旅游
题号：NC249075
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 n 个城市，m 条连接两个城市的双向道路，每条道路有个损坏值 a_i，牛牛手里有 c 元，进行第 k 次修复道路操作时需要 k\times a_i 元，国家愿意修复损坏值 \le p 的道路，牛牛不需要再花钱修国家帮忙修的路。问 p 至少为多少，牛牛有能力使得任意两座城市间可以通过修好的道路互相到达。如国家不需要修复任何道路，输出 0。

输入描述:

第一行三个正整数 n,m,c(1\le n\le4\times10^4,1\le m\le10^5,1\le c\le10^{18})。
接下来 m 行，每行 3 个正整数 x,y,a_i(1\le x,y\le n,1\le a_i\le10^9)，表示有一条连接 x,y 城市的双向道路损坏值为 a_i。保证无重边，无自环，图连通。

输出描述:

输出一行一个正整数，表示完成目标所需 p 的最小值。
示例1

输入

复制 
4 6 7
1 2 3
1 3 4
1 4 6
2 3 2
2 4 1
3 4 5

输出

复制 
1

说明

p=1 时，2,4 号城市可以互相到达，第一次操作修复连接 1,2 的道路，花费 1\times3 元，第一次操作修复连接 2,3 的道路，花费 2\times2 元，共花费 7 元，能达成目标。