KD-Graph

Problem 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.

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.

Sample Input

2

3 2 2

1 2 3

2 3 5

3 2 2

1 2 3

2 3 3

Sample Output

3

-1

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）