JOI 공원

면접 대비

시간 제한1초메모리 제한256 MB

요약

1번 정점에서 거리 X 이내 정점을 지하철로 묶을 때 건설비 C와 X를 곱한 값과 밖에 남은 도로 길이 합이 최소가 되는 값을 구합니다.

난이도: 보통10점 중 6점
유형: 최단 경로, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

20XX년 IOI나라에서 열리는 올림픽을 준비하면서 JOI공원을 정비하기로 했다. JOI공원에는 광장이 $N$ 개 있고 1번부터 $N$ 번까지 번호가 붙어 있다. 광장을 잇는 도로는 $M$ 개 있고 1번부터 $M$ 번까지 번호가 붙어 있다. 도로 $i$ ( $1 \le i \le M$ )는 광장 $A_i$ 와 광장 $B_i$ 를 양방향으로 잇고, 길이는 $D_i$ 이다. 어느 광장에서 출발해도 도로를 따라 다른 모든 광장으로 갈 수 있다.

정비 계획은 다음과 같다. 지하도 설치에 관한 값 $C$ 가 주어진다. 먼저 0 이상의 정수 $X$ 를 하나 고르고, 광장 1에서 거리가 $X$ 이하인 광장을 광장 1까지 포함해 모두 지하도로 잇는다. 광장 $i$ 와 광장 $j$ 의 거리는 광장 $i$ 에서 광장 $j$ 까지 가는 경로에 쓰인 도로 길이의 합 중 최솟값이다. 지하도를 설치하는 비용은 전부 합쳐 $C \times X$ 이다.

다음으로 지하도로 이어진 광장끼리 잇는 도로를 전부 철거한다. 도로를 철거하는 데에는 비용이 들지 않는다.

마지막으로 철거하지 않고 남은 도로를 전부 보수한다. 길이가 $d$ 인 도로를 보수하는 비용은 $d$ 이다.

정비를 시작하기 전 JOI공원에 지하도는 없다. JOI공원의 광장과 도로 정보, 지하도 설치에 관한 값이 주어질 때 JOI공원을 정비하는 데 드는 비용의 최솟값을 구하는 프로그램을 작성하여라.

입력

표준 입력으로 다음 정보가 주어진다.

첫 줄에 정수 $N$ , $M$ , $C$ 가 공백으로 구분되어 주어진다. 광장이 $N$ 개, 도로가 $M$ 개 있고 지하도 설치에 관한 값이 $C$ 라는 뜻이다.
이어지는 $M$ 개 줄에 정수 $A_i$ , $B_i$ , $D_i$ ( $1 \le i \le M$ )가 공백으로 구분되어 한 줄씩 주어진다. 도로 $i$ 가 광장 $A_i$ 와 광장 $B_i$ 를 잇고 그 길이가 $D_i$ 라는 뜻이다.

출력

JOI공원을 정비하는 데 드는 비용의 최솟값을 한 줄로 출력한다.

제한

$2 \le N \le 100000$
$1 \le M \le 200000$
$1 \le C \le 100000$
$1 \le A_i \le N$ ( $1 \le i \le M$ )
$1 \le B_i \le N$ ( $1 \le i \le M$ )
$A_i \ne B_i$ ( $1 \le i \le M$ )
$(A_i, B_i) \ne (A_j, B_j)$ 이고 $(A_i, B_i) \ne (B_j, A_j)$ ( $1 \le i < j \le M$ )
$1 \le D_i \le 100000$ ( $1 \le i \le M$ )
어느 광장에서 출발해도 도로를 따라 다른 모든 광장으로 갈 수 있다.

예제3

예제 1
입력
```
5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5
```
예상 출력
```
14
```
예제 2
입력
```
5 4 10
1 2 3
2 3 4
3 4 3
4 5 5
```
예상 출력
```
15
```
예제 3
입력
```
6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5
```
예상 출력
```
10
```