题目描述

给定一张 \(n\) 个节点， \(m\) 条边的无向图，保证给定的图无环（是森林），第 \(i\) 条边连接节点 \(u_i\) 和 \(v_i\)，长度为 \(w_i\)。

你需要增加 \(n-m-1\) 条边，使这张图联通（变成一棵树），增加的边长度均为正整数，并且这 \(n-m-1\) 条边的长度总和至少为 \(S\)，你希望加边后得到的树直径尽可能小。

你只需要输出最小的直径。

注：我们定义树上点对距离为两点间简单路径经过的边权之和，定义树的直径为树上最大的点对距离。

输入格式

第一行输入一个整数 \(T\)，表示数据组数。

对于每组数据：

第一行输入三个整数 \(n, m, S\)，表示图的节点数，边数和增加的边长度总和的最小值。

接下来 \(m\) 行，每行输入三个整数 \(u_i, v_i, w_i\)，表示第 \(i\) 条边连接的两个节点标号和这条边的长度。

令 \(N_{tot}\) 表示所有测试组 \(n\) 之和。

\(1 \le T \le 1000, N_{tot} \le 2.1 \times 10^5\)。

对于每组数据： \(2 \le n \le 10^5, 0 \le m \lt n-1, 1 \le w_i, S \le 10^9\)。

保证输入的图是森林，并且图不连通（至少需要加 \(1\) 条边）。

输出格式

对于每组数据：

输出单个整数表示直径的最小值。

样例输入

3
4 2 3
1 2 2
2 3 3
6 3 5
1 2 2
2 3 3
4 5 2
6 3 6
1 2 2
2 3 3
4 5 2

样例输出

6
7
8