Minimizing the Maximum Travel Time in a Forest Graph

In the beginning of the world, when IOI was still a distant dream, Serpent inhabited an area with (N) waterholes numbered from (0) to (N-1) and (M) bidirectional trails connecting some pairs of waterholes. Each trail takes a fixed number of days to traverse (different trails may require different travel times). It is guaranteed that between any two waterholes there is at most one path (which may consist of one or more trails), and some waterholes might not be connected at all (i.e. (M \leq N-1)).

Serpent’s friend, Kangaroo, plans to construct exactly (N-M-1) additional trails such that the entire graph becomes connected. Kanagroo can build a trail between any two waterholes, and every new trail takes exactly (L) days to traverse. The goal is to choose the locations for these new trails so that the maximum travel time (i.e. the diameter of the graph) between any two waterholes is minimized in the final connected graph.

More formally, let the original forest have several connected components (trees). For each tree, define its diameter as the maximum distance between any two nodes in that tree, and its radius as (\lceil\frac{\text{diameter}}{2}\rceil). After connecting the trees with (N-M-1) new edges (each with weight (L)), if we let (r_1 \ge r_2 \ge \cdots \ge r_k) be the radii of the (k) components and (D) be the maximum diameter among all components, then the optimal answer is given by: [ \text{answer} = \max\Bigg(D,; r_1 + r_2 + L,; \Big( r_2 + r_3 + 2L \Big)\Bigg)] when (k \ge 3), and a similar formula holds when (k = 2) (the last term is ignored). When (k = 1), no new edge is added and the answer is simply (D).

Your task is to compute this minimized maximum travel time after the optimal addition of new trails.

inputFormat

The first line contains three integers (N), (M), and (L) separated by spaces. (N) is the number of waterholes, (M) is the number of original trails, and (L) is the travel time for each new trail. Each of the next (M) lines contains three integers (u), (v), and (t), indicating that there is a bidirectional trail between waterhole (u) and waterhole (v) that takes (t) days to traverse.

outputFormat

Output a single integer representing the minimized maximum travel time (in days) between any two waterholes after optimally constructing the new trails.

sample

4 2 3
0 1 4
2 3 2

6