Background

Special for beginners, ^_^

Description

Let’s call a weighted connected undirected graph of n vertices and m edges KD-Graph, if the following conditions fulfill:

• $n$ vertices are strictly divided into $K$ groups, each group contains at least one vertice

• if vertices $p$ and $q ( p ≠ q )$ are in the same group, there must be at least one path between $p$ and $q$ meet the max value in this path is less than or equal to $D$.

• if vertices $p$ and $q ( p ≠ q )$ are in different groups, there can’t be any path between $p$ and $q$ meet the max value in this path is less than or equal to $D$.

You are given a weighted connected undirected graph $G$ of $n$ vertices and $m$ edges and an integer $K$.

Your task is find the minimum non-negative $D$ which can make there is a way to divide the $n$ vertices into $K$ groups makes $G$ satisfy the definition of KD-Graph.Or $−1$ if there is no such $D$ exist.

Format

Input

The first line contains an integer $T (1≤ T ≤5)$ representing the number of test cases. For each test case , there are three integers $n,m,k(2≤n≤100000,1≤m≤500000,1≤k≤n)$ in the first line. Each of the next m lines contains three integers $u,v$ and $c (1≤v,u≤n,v≠u,1≤c≤10^9)$ meaning that there is an edge between vertices $u$ and $v$ with weight $c$.

Output

For each test case print a single integer in a new line.

Samples

2
3 2 2
1 2 3
2 3 5
3 2 2
1 2 3
2 3 3

3
-1