Informatica Online Judge

  GOI 본선 [0389 / 0185]

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


The Champion of this Problem (C++) : gs17082 - ms / 701byte
My Best Submission (C++) : N/A

[]

Background

GSHS국에는 N개의 도시가 있고, 1~N까지의 번호가 붙어 있다. 또, M개의 도로가 있다. 모든 도로는 서로 다른 두 도시를 연결한다. 물론 양방향 모두 통행이 가능한 도로이다. GSHS국의 임의의 두 도시는 모두 이 도로망을 통해서 도달할 수 있다. GSHS국의 도로는 모두 유료도로이다. 도로마다 통행료가 정해져 있다.

GSHS국에도 물론 GOI(GSHS Olympiad in Informatics)라는 대회가 열린다. GSHS국의 GOI 본선은 각 도시의 대표선수가 1명씩 출전한다. 본선을 어느 도시에서 개최할지를 결정하고, 선수를 개최도시로 모으기 위해서 드는 도로 교통비를 계산할 필요가 있다. 본선은 총 K개의 도시에서 개최하고, 본선대회 때에는 모든 선수를 각각 K개의 개최 도시 중 한 도시로 이동하지 않으면 안된다. 1개의 도시에 모일 수 있는 선수의 인원 제한은 없다.

본선을 개최하는 도시에 선수를 모으기 위해서는 도로를 이용해야 하고, 통행요금이 c인 도로는 한 번에 몇 명이 지나가든지 간에 요금은 c원이다. 여기서, 선수를 이동시키는 순서를 어떻게 하느냐에 따라서 여러 명의 선수를 한 번에 통행시키도록 하면 요금을 절약할 수 있을 것이다.

본선을 개최하는 도시를 결정하고, 선수를 본선대회가 열리는 각 도시로 모으는데 드는 통행요금의 합의 최소값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 정수 N(1<=N<=100,000), M(1<=M<=100,000), K(1<=K<=N)가 공백으로 구분되어 입력된다.

(N은 도시의 수, M은 도로의 수, K는 본선을 개최하는 도시의 수이다.)

두 번째 줄부터 M줄에 걸쳐서 Ai, Bi, Ci가 입력된다. 이는 A도시에서 B도시까지를 연결하는 도로를 나타내고 C는 통행료를 나타낸다.

(단, 1 <= Ai < Bi <= N, 1 <= Ci <= 100 )

Output

모든 선수들을 K개의 대회장으로 모으는데 드는 최소의 통행요금을 출력한다.

IO Example

입출력 예시 1

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

출력
16


설명)
예를 들어 도시 1에서 본선을 개최한다고 하면, 우선 도시 4의 대표선수를 도시 2로 이동시키고 다음으로 도시 3의 대표선수를 도시 2로 이동 시켜, 도시 2에 있는 3명의 선수를 도시 1로 이동시키는 것이 최소 금액이 된다.


입출력 예시 2

입력
5 6 2
1 2 5
1 3 3
2 3 4
2 5 7
3 4 6
4 5 5

출력
12



설명)

예를 들어 도시 3과 도시 4에서 본선을 개최한다라고 하면, 도시 1, 2의 대표선수는 도시 3으로, 도시 5의 대표선수는 도시 4로 모이면 된다.

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