4464 - 슈퍼마켓

• Submit
• Status
• Discuss
• Summary

Description

어떤 기업이 슈퍼마켓을 세우려고 합니다. 슈퍼마켓은 기존의 도로망을 이용하여 각 도시로부터 슈퍼마켓이 위치 할 도시까지의 거리의 합이 최소가 되는 위치에 세워질 예정입니다. 기존의 도로망에서 모든 도시들은 연결되어있으며, 두 도시를 잇는 도로는 최대 한 개입니다. 슈퍼마켓의 위치를 찾아주세요. 

Input

* Line 1 : 도시의 수V 도로의 수E 

• 1 ≤ V ≤ 500
• 1 ≤ E ≤ 100,000

* Line 2 ~ E+1 : V1 V2 W

• V1, V2 : 도로가 잇는 두 도시의 번호 (0~V-1 범위의 정수)
• W : 두 도시 간의 거리 (1~1,000 범위의 정수) 

* 거리의 합은 계산도중 int의 범위를 넘지 않음.

Output

* Line 1 : 슈퍼마켓이 위치할 도시의 번호. 만약 슈퍼마켓이 위치할 수 있는 도시가 두 개 이상이라면 가장 작은 번호를 출력한다.

Sample Input

5 8
3 2 6
0 1 4
1 2 11
4 3 6
0 3 1
2 1 10
4 0 27
1 4 10

Sample Output

3

Source

c자료구조10장