본선 회장 (Finals)

JOI 나라에는 $N$개의 도시가 있고, $1$부터 $N$까지 번호가 붙어 있다. 또 $M$개의 도로가 있다. 모든 도로는 서로 다른 두 도시를 잇고, 양방향으로 통행할 수 있다. JOI 나라의 임의의 두 도시는 도로를 따라 한쪽에서 다른 쪽으로 도달할 수 있다. JOI 나라의 도로는 모두 유료 도로이고, 도로마다 통행료가 정해져 있다.

JOI 나라에서도 정보 올림피아드가 열린다. JOI 나라 정보 올림피아드 본선에는 각 도시의 대표 선수가 출전한다. 본선을 어느 도시에서 열지 결정하고, 선수를 그 도시에 모으는 데 드는 금액을 미리 견적해 두어야 한다. 본선은 $K$개의 도시에서 열리고, 본선을 열 때에는 모든 선수를 그 중 어느 한 도시로 이동시켜야 한다. 한 도시에 모이는 선수의 수에는 제한이 없다.

본선을 여는 도시에 선수를 모을 때에는 도로를 이용한다. 통행료가 $c$인 도로는 한 번에 몇 명이 통행해도 요금은 $c$이다. 따라서 선수를 이동시키는 순서를 잘 정해서 여러 선수를 한 번에 통행시키면 요금을 절약할 수 있다.

본선을 여는 도시를 정하고, 선수를 본선 회장에 모을 때 드는 통행료의 합을 최소화하려고 한다.

$N$, $M$, $K$와 모든 도로의 정보가 주어졌을 때, 선수를 본선 회장에 모을 때 드는 통행료의 합의 최솟값을 계산하는 프로그램을 작성하시오.

표준 입력에서 다음 입력을 읽는다.

• 첫째 줄에는 정수 $N$, $M$, $K$가 공백을 구분으로 쓰여 있다.
• 이어지는 $M$개의 줄에는 한 줄에 하나의 도로에 대한 정보가 쓰여 있다. 이 줄들 중 $i$번째 줄은 도로 $i$에 대한 정보이고, 정수 $A_i$, $B_i$, $C_i$가 공백을 구분으로 쓰여 있다.

표준 출력에 선수를 본선 회장에 모을 때 드는 금액의 최솟값을 나타내는 정수 하나를 출력하시오.

• $1 \le N \le 100{,}000$ (도시의 수)
• $1 \le M \le 100{,}000$ (도로의 수)
• $1 \le K \le N$ (본선을 여는 도시의 개수)
• $1 \le A_i < B_i \le N$ (도로 $i$가 잇는 두 도시)
• $1 \le C_i \le 100$ (도로 $i$의 통행료)