JOI 공원

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$)
• 어느 광장에서 출발해도 도로를 따라 다른 모든 광장으로 갈 수 있다.