PKU 2395(Out of Hay) 번역-USACO 2005 March Silver

시간 제한 1초

메모리 제한 65536K

문제 설명

소가 먹을 건초가 바닥났다. 이런 긴급 상황에는 발빠른 조치가 필요하다. 그래서 Bessie는 다른 농장으로 가서 건초가 얼마나 있는지 조사하고자 한다. N가의 농장이 있으며 베시는 1번 농장부터 방문할 것이다. 베시는 농장 간에 연결된 M개의 왕복 도로(도로의 길이는 1,000,000,000을 초과하지 않음) 중 일부 또는 모두를 건너다닐 것이다. 어떤 농장은 각각 다른 길이의 길로 다양하게 연결되어 있을 수도 있다. 모든 농장은 1번 농장과 하나 이상의 길로 연결되어 있다.

 Bessie는 얼마나 큰 가죽 물통이 필요한지 결정하려고 하고 있다. 그녀는 한 유닛의 길에 1온스의 물이 필요하다는 것을 안다. 각 농장에서 물은 더 구할 수 있기 때문에 가장 긴 거리의 길에 대해서 걱정하고 있다. 물론, Bessie는 농장간의 경로를 미리 정해서 운반하는 물의 양을 최소화할 것이다.

 베시가 다음의 사실을 알 수 있도록 도와주어라. Bessie가 최대 얼마만큼의 물을 들고 가야 하는가? 그리고 Bessie가 최소의 거리를 선택할 것이라는 가정 하에 Bessie가 가게 될 두 농장간의 거리 중 가장 먼 거리는 얼마인가? 물론 Bessie는 지나가야 하는 길의 경로를 최소화하기 위하여 왔던 길을 되돌아 갈 수도 있다.

입력

Line 1:두 정수 N,M(2<=N<=2,000, 1<=M<=10,000)

Line 2~M+1:세 정수 A_i,B_i,L_i. A_i에서 B_i까지 가는데 L_i만큼의 거리를 가야한다는 것

출력

길을 가로지르기 위해 필요한 가장 긴 거리를 나타내는 하나의 정수를 출력한다.

입력 예제

3 3

1 2 23

2 3 1000

1 3 43

출력 예제

43

http://poj.org/problem?id=2395