A91490.Welcome24ever 和水坑

天地之初，IOI 还只是遥远的梦想。

Welcome24ever 生活的地方有 $N$ 个水坑，编号为 $0, 1, \dots, N-1$，有 $M$ 条双向小路连接这些水坑。
每两个水坑之间至多有一条路径（路径包含一条或多条小路）可以互相到达，因此这些小路形成了一片森林；有些水坑之间根本无法互通（即 $M \le N-1$）。

Welcome24ever 走过每条小路需要一个固定的天数，不同的小路所需的时间可能不同。

他的朋友 fangz 想要新修 $N - M - 1$ 条小路，使得新修完成后，Welcome24ever 可以在任意两个水坑之间互相到达（也就是整个图连通）。
fangz 可以在任意两个水坑之间修路，Welcome24ever 通过每一条新路的时间都是 $L$ 天。

fangz 希望找到一种修路方式，使得修完之后，从任意一个水坑到另一个水坑的最短路时间中的最大值尽可能小（也就是让“直径”尽量小）。

• 第 $1$ 行：三个整数 $N, M, L$：

  • $N$ —— 水坑的数量；
  • $M$ —— 原本存在的小路数量；
  • $L$ —— 每条新修小路的通过时间。

• 第 $2$ 行到第 $M+1$ 行：每行三个整数 $A[i], B[i], T[i]$，表示一条现有的小路：

  • 小路连接水坑 $A[i]$ 和水坑 $B[i]$；
  • 通过这条小路需要 $T[i]$ 天。

水坑编号为 $0 \sim N-1$。
原图中任意两点之间至多存在一条简单路径（即原图是一个森林）。

输出一个整数，表示在合理修建 $N-M-1$ 条新小路之后，从任意一个水坑到另一个水坑的最短路时间中的最大值（也就是最终图的最小可能直径）。

对这组数据的一种最优修路方式是新修三条小路：

• 在水坑 $1$ 和 $2$ 之间；
• 在水坑 $1$ 和 $6$ 之间；
• 在水坑 $4$ 和 $10$ 之间。

新修完成后，所有水坑之间连通，从水坑 $0$ 到水坑 $11$ 的最短路径长度为 $18$ 天，是所有点对之间最短路中最大的值。可以证明这是最优答案。

数据范围

• $1 \le N \le 10^5$；
• $0 \le M \le N-1$；
• $0 \le A[i], B[i] \le N-1$；
• $1 \le T[i] \le 10^4$；
• $1 \le L \le 10^4$。