빌라봉

이 이야기는 IOI라는 대회가 존재하리라고는 상상조차 할 수 없었던, 세상의 태초에 있었던 아주 먼 옛날의 일이다.

$0, 1, \ldots, N-1$ 번으로 번호가 매겨진 $N$ 개의 빌라봉(호수)이 있는 땅에 큰 뱀 한 마리가 살고 있다. 이 땅에는 $M$ 개의 길이 있으며, 각 길은 두 빌라봉을 잇고 뱀은 이 길을 양방향으로 지나갈 수 있다. 임의의 두 빌라봉은 길을 따라 (직접 또는 여러 길을 거쳐) 많아야 한 가지 경로로만 연결되어 있으며, 서로 전혀 연결되지 않은 빌라봉 쌍이 있을 수도 있다. 따라서 $M \le N - 1$ 이다. 뱀이 길 하나를 지나는 데에는 며칠이 걸리며, 이 시간은 길마다 다를 수 있다.

뱀의 친구인 캥거루는 $N - M - 1$ 개의 새로운 길을 놓아 모든 빌라봉 쌍이 서로 오갈 수 있도록 만들려 한다. 캥거루는 원하는 두 빌라봉을 골라 그 사이에 길을 놓을 수 있으며, 캥거루가 새로 놓은 길을 지나는 데에는 항상 $L$ 일이 걸린다.

또한 캥거루는 뱀이 최대한 빠르게 이동하기를 바란다. 그래서 캥거루는 임의의 두 빌라봉 사이를 오가는 데 걸리는 시간의 최댓값이 가능한 한 작아지도록 길을 놓으려 한다. 캥거루가 이렇게 길을 모두 놓은 뒤, 두 빌라봉 사이를 오가는 데 걸리는 최대 시간을 구하시오.

위 그림에는 $N = 12$ 개의 빌라봉과 $M = 8$ 개의 길이 있다. 새로 놓는 길을 지나는 데에는 $L = 2$ 일이 걸린다고 하자. 이때 캥거루는 다음과 같이 세 개의 길을 놓을 수 있다.

• 빌라봉 1과 2 사이
• 빌라봉 1과 6 사이
• 빌라봉 4와 10 사이

모든 길을 놓은 뒤의 모습이 위 그림에 나타나 있다. 이때 두 빌라봉 사이의 최대 이동 시간은 (빌라봉 0과 11 사이의) 18일이며, 이것이 가능한 가장 작은 값이다. 즉 캥거루가 어떤 방식으로 새 길을 놓더라도, 뱀이 오가는 데 18일 이상 걸리는 빌라봉 쌍이 항상 존재한다.

첫째 줄에 세 정수 $N$, $M$, $L$ 이 공백으로 구분되어 주어진다. 이어지는 $M$ 개의 줄 각각에는 이미 존재하는 길 하나를 나타내는 세 정수 $A$, $B$, $T$ 가 주어진다. 이는 빌라봉 $A$ 와 빌라봉 $B$ 를 잇는 길이며, 이 길을 지나는 데에는 양방향 모두 $T$ 일이 걸린다는 뜻이다.

• $N$: 빌라봉의 개수
• $M$: 이미 존재하는 길의 개수
• $L$: 뱀이 새로 놓인 길 하나를 지나는 데 걸리는 시간(일 단위)
• $A$, $B$, $T$: 각 길이 잇는 두 빌라봉과 그 길을 지나는 데 걸리는 시간

모든 빌라봉이 서로 연결되면서 두 빌라봉 사이의 최대 이동 시간이 최소가 되도록 $N - M - 1$ 개의 길을 놓았을 때, 그 최대 이동 시간을 한 줄에 출력한다.

• $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$