Informatica Online Judge

  요충지 [2141 / 085D]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16102]

Background

어느 날, 지구에 외계 문명의 용기병들이 공격을 해 왔다.

총사령관인 경곽이는 인류를 지키기 위해 지도를 펼쳐 보았다. 지도에는 n개의 도시와 양방향 통행이 가능한 m개의 도로가 있다.인류는 1번 도시에 살고, 용기병들은 n번 도시에 상륙했다.

경곽이는 용기병들을 막을 병력을 충원하기 위해, 용기병들이 오기 전 시간을 끌려고 한다.

다행히도 경곽이에게는 도시 하나를 통과하지 못하게 만들기에는 충분한 지뢰와, 그 지뢰를 신속하게 매설할 자동차들이 있다.

그러나 그 지뢰들을 분산시키기에는 위험도가 너무 커서, 지뢰는 딱 한 도시에 모두 매설할 것이다.

그리고 시간을 끌기 위해 사용하는 지뢰들이므로 1번 도시에는 지뢰를 심지 않고, 자동차들이 용기병과 만나면 임무를 완수하지 못하기 때문에 n번 도시에도 지뢰를 심지 않는다.

경곽이는 당연히도 가장 중요한 곳, 그러니까 가장 시간을 잘 끌 수 있는 곳에 지뢰를 매설하기를 원한다. 경곽이를 도와 지뢰를 매설할 요충지를 찾자.

Input

첫째 줄에는 도시의 개수 n(3<=n<=10000)과 도로의 개수 m(m<=100000)이 주어진다.4

두 번째 줄부터 m+1번째 줄까지는 도로가 연결하는 두 도시의 번호와 도로의 길이 k(1<=k<=1000)가 주어진다.

맨 처음 주어진 상태에서 연결되지 않는 경우는 없다.

Output

지뢰를 심을 도시의 번호를 출력한다. 만약 후보가 여러 개라면, 가장 작은 번호를 출력한다.

IO Example

입력1
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40

출력1
3

입력2
13 20
1 2 40
2 3 30
1 3 50
3 4 50
4 5 40
5 6 30
4 6 50
6 13 50
13 12 40
12 11 30
11 13 50
11 10 50
10 9 40
9 8 30
8 10 50
8 1 50
1 7 70
4 7 70
10 7 70
13 7 70

출력2
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]