Informatica Online Judge

  천도 (Small) [1265 / 04F1]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 24   Total Tried : 337


The Champion of this Problem (C++) : identity230c - 0ms / 1241byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

GSHS는 하나의 수도와 수도를 포함한 n개의 도시로 구성된 도시이다.

GSHS의 수도는 1번 도시이다. 그리고 이 n개의 도시는 m개의 도로로 연결되어 있다.

GSHS의 모든 도시에서 다른 도시로 m개의 도로를 이용하여 이동할 수 있다.

경곽이는 GSHS국의 수도인 1번 도시에 살고 있다. 경곽이는 이번 연구주제로 수도의 접근성에 대해서 연구하고 있다.

경곽이는 수도의 접근성을 다음과 같이 정의하고 있다.

i번째 도시에서 수도와의 거리를 w_i라고 할 때,

for i = 1 to n
수도의 접근성 += w_i


접근성은 적을 수록 좋다.

경곽이는 현재 수도의 접근성과 다른 도시들이 수도가 될 때의 접근성의 비교에 대해서 연구하고 있다.

만약 현재 수도보다 접근성이 좋은 도시가 있다면 천도를 제안하고자 연구를 진행하고 있다.

현재 수도보다 천도를 할 때, 새로운 수도의 접근성을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 GSHS의 도시의 수를 나타내는 정수 n과 도로의 수 m이 입력된다.

두 번째 줄부터 m개의 줄에 걸쳐서 각 도로의 정보가 주어진다. 각 도로는 양방향 이동가능하며, 연결되는 두 도시 a, b와 거리 w가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 200
1 <= a, b <= n
1 <= w <= 10,000

Output

새로 천도한 수도의 접근성을 출력한다. 만약 천도하더라도 현재의 수도 접근성이 좋아지지 않는다면 -1 을 출력한다.

IO Example

입력
5 4
1 2 1
2 3 2
3 4 2
4 5 1

출력
10

*해설
3번 도시를 수도로 하면 1에서 3까지 3, 2에서 3까지 2, 4에서 3까지 2, 5에서 3까지 3으로 모두 합하면 10이다. 이보다 더 접근성이 좋은 도시는 없다.

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