Billabongs

Time limit1sMemory limit256 MB

Summary

Connect the weighted forest into one network with fixed-cost links so the longest travel time between any two ponds is as small as possible.

Level: Medium7 of 10
Topics: Tree, Greedy, Sorting
Solved: No attempts yet

Problem

This story takes place at the very beginning of the world, in an age so distant that no one could yet dream of a contest called the IOI.

In a land of $N$ billabongs (ponds) numbered $0, 1, \ldots, N-1$ there lives a great snake. The land has $M$ roads; each road connects a pair of billabongs, and the snake can travel along it in either direction. Any pair of billabongs is connected by at most one path of roads (directly or indirectly), and some pairs may not be connected at all, so $M \le N - 1$ . Traversing a single road takes the snake a number of days, and this number can differ from road to road.

The snake's friend, a kangaroo, wants to build $N - M - 1$ new roads so that every pair of billabongs becomes reachable from one another. The kangaroo may pick any two billabongs and build a road between them, and traversing a road built by the kangaroo always takes $L$ days.

The kangaroo also wants the snake to travel as quickly as possible, so it will build the roads so that the maximum travel time between any two billabongs is as small as possible. After the kangaroo has built all of its roads, compute this maximum travel time between two billabongs.

In the figure above there are $N = 12$ billabongs and $M = 8$ roads. Suppose that traversing a newly built road takes $L = 2$ days. Then the kangaroo can build the following three roads:

between billabongs 1 and 2,
between billabongs 1 and 6,
between billabongs 4 and 10.

The figure above shows the land after all roads have been built. Here the maximum travel time between two billabongs is 18 days (between billabongs 0 and 11), which is the smallest value possible. That is, no matter how the kangaroo builds the new roads, there is always a pair of billabongs whose travel time is at least 18 days.

Input

The first line contains three integers $N$ , $M$ , and $L$ separated by spaces. Each of the next $M$ lines contains three integers $A$ , $B$ , and $T$ describing one existing road: it connects billabong $A$ and billabong $B$ , and traversing it takes $T$ days in either direction.

$N$ : the number of billabongs
$M$ : the number of already existing roads
$L$ : the time in days for the snake to traverse one newly built road
$A$ , $B$ , $T$ : the two billabongs joined by each road and the time to traverse it

Output

Print, on a single line, the maximum travel time between two billabongs after $N - M - 1$ roads are built so that all billabongs are connected and this maximum travel time is minimized.

Constraints

$1 \le N \le 100000$
$0 \le M \le N - 1$
$0 \le A, B \le N - 1$
$1 \le T \le 10000$
$1 \le L \le 10000$

Examples3

Example 1

Input

Expected output

Example 2
Input
```
1 0 5
```
Expected output
```
0
```
Example 3
Input
```
2 0 7
```
Expected output
```
7
```