정복자

서강 나라는 $N$개의 도시와 $M$개의 도로로 이루어져 있다. 도로는 모두 양방향이고, 어느 두 도시 사이에도 도로를 따라가는 경로가 있다. 도로마다 지나는 데 드는 비용이 정해져 있다. 도시에는 $1$번부터 $N$번까지 번호가 붙어 있고, $1$번 도시의 군주 박건은 모든 도시를 정복하려 한다.

처음에 점거한 도시는 $1$번 도시뿐이다. 도시 $B$를 정복하려면 $B$와 도로로 이어진 도시 가운데 적어도 하나를 이미 정복하고 있어야 한다. 조건을 만족하는 도시 중 하나인 $A$를 고르면, $B$를 정복하는 과정에서 $A$와 $B$를 잇는 도로의 비용이 든다. 박건은 한 번에 한 도시씩 정복을 시도하고 언제나 성공한다. 도시가 하나 정복될 때마다 남은 도시가 경계 태세에 들어가서 모든 도로의 비용이 $t$만큼 오른다. 한 번 정복한 도시는 다시 정복하지 않는다.

박건이 모든 도시를 정복하는 데 드는 최소 비용을 구하라.

첫째 줄에 도시의 수 $N$, 도로의 수 $M$, 정복이 한 번 일어날 때마다 오르는 도로 비용 $t$가 주어진다. $N$은 $10000$ 이하의 자연수, $M$은 $30000$ 이하의 자연수, $t$는 $10$ 이하의 자연수이다.

이어지는 $M$개의 줄에는 도로를 나타내는 자연수 세 개 $A$, $B$, $C$가 주어진다. $A$번 도시와 $B$번 도시를 잇는 비용 $C$의 도로가 있다는 뜻이다. $A$와 $B$는 서로 다른 $N$ 이하의 자연수이고, $C$는 $10000$ 이하의 자연수이다. 같은 두 도시를 잇는 도로가 여러 개 있을 수도 있다.

모든 도시를 정복하는 데 드는 최소 비용을 출력한다.

첫 번째 예제에서는 먼저 $1$번 도시와 이어진 $3$번 도시를 정복한다. 정복하는 데 $2$의 비용이 든다. $3$번 도시를 정복한 뒤 모든 도로의 비용이 $8$만큼 오른다. 지금 점거한 도시는 $1$번과 $3$번이다.

$4$번 도시는 점거하고 있는 $3$번 도시와 이어져 있어서 $3$번 도시에서 정복할 수 있고, $3$번 도시와 $4$번 도시를 잇는 도로의 비용 $1+8$이 든다. 점거한 도시는 $1$번, $3$번, $4$번이 된다.

$2$번 도시도 점거하고 있는 $3$번 도시와 이어져 있어서 정복할 수 있다. 정복하는 과정에서 $2$번 도시와 $3$번 도시를 잇는 도로의 비용 $2+8+8$이 든다. 이렇게 하면 모든 도시를 정복한다.

결과적으로 $2 + (1+8) + (2+8+8) = 29$의 비용이 든다.