TopCoder

User's AC Ratio

69.0% (20/29)

Submission's AC Ratio

30.0% (48/160)

Description

當大地仍在創始,IOI連影子都不存在時期,發生了以下的故事。

水蛇(Serpent)住在一處擁有N個水洞的地方,水洞編號為 0, …, N - 1 。除此之外,有 M條雙向初始路徑,每條路徑連結一組的水洞讓水蛇可以通過。每一個水洞(不論直接或是間接)至多被一條路徑序列給連結著,但仍然有水洞可能都沒被任何的路徑給連結到(所以 M ≤ N-1 )。每條路徑會花掉水蛇特定的天數來通過,通過時間每條路徑有可能會不一樣。

水蛇的好友,袋鼠(Kangaroo),希望可以挖出 N - M - 1 條新的路徑,讓水蛇可以在任意兩個水洞之間遊走。袋鼠可以在任意兩個水洞之間挖出新的路徑,而由袋鼠挖出的路徑,水蛇需要 L 天就可以通過。

另外,袋鼠希望水蛇在各水洞之間盡可能的快速移動。袋鼠將會挖出新的路徑,使得旅行於任兩個水洞之間所需要的時間最短。在袋鼠挖出新的路徑後,請你幫助水蛇和袋鼠計算出各水洞之間最長移動時間為何。

此為範例測資的圖。

Input Format

本題有豆比測資,讀到「以歐哀夫」結束。
對於每比測資,第一行有三個數字N M L,分別表示水洞數目、初始路徑數、水蛇在新挖出的路徑移動所需的天數。

接下來有 M 行,每行三個數字Ai Bi Ti,表示第i個路徑連結著水洞Ai與水洞Bi,且需要Ti天的時間來通過。

限制:
1 ≤ N ≤ 100,000
0 ≤ M ≤ N-1
0 ≤ Ai, Bi ≤ N-1
1 ≤ Ti ≤ 10,000
1 ≤ L ≤ 10,000

14%的測資,M = N - 2 ,每個水洞只連有一條或是兩條的初始路徑。換句話說,只存在著兩組的相連水洞,每組相連的水洞中不存在分岔的路徑。
10%的測資,M = N-2 和 N ≤ 100。
23%的測資,M = N ­-2。
18%的測資,每個水洞至多連有一條初始路徑。
12%的測資,N ≤ 3,000。
23%的測資,沒有限制。

Output Format

輸出一個數字,表示在袋鼠挖出新的路徑後所有水洞之間的最大的移動時間(如敘述)。

Sample Input

12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

Sample Output

18

Hints


上圖展示了最終的路徑圖。最長的移動時間是從水洞0移動到水洞11,需18天。
這已經是最低所需時間—無論袋鼠怎麼改變挖路徑的方法,都會產生至少一組水洞使得水蛇需要花費18天以上(含)才能通過。

Problem Source

IOI 2013

Subtasks

For Testdata: 0 ~ 0, Score: 1
For Testdata: 1 ~ 1, Score: 14
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 23
For Testdata: 4 ~ 4, Score: 18
For Testdata: 5 ~ 5, Score: 12
For Testdata: 6 ~ 6, Score: 22
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536