KD-Graph

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.

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

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

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

3
-1

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