Conqueror

The land of Seogang consists of $N$ cities and $M$ roads. Every road is bidirectional, and between any two cities there is a path that follows roads. Each road has a cost you pay to use it. The cities are numbered from $1$ to $N$, and Park Geon, the ruler of city $1$, wants to conquer every city.

At the start he holds city $1$ only. To conquer a city $B$, he must already hold at least one of the cities joined to $B$ by a road. Once he picks such a city $A$, conquering $B$ costs the cost of the road between $A$ and $B$. Park Geon attempts one city at a time and always succeeds. Each time a city falls, the remaining cities go on alert and the cost of every road rises by $t$. A city that has been conquered is never conquered again.

Find the minimum total cost for Park Geon to conquer every city.

The first line contains the number of cities $N$, the number of roads $M$, and the amount $t$ by which every road cost rises after each conquest. $N$ is a natural number at most $10000$, $M$ is a natural number at most $30000$, and $t$ is a natural number at most $10$.

Each of the next $M$ lines contains three natural numbers $A$, $B$, $C$ describing a road: there is a road of cost $C$ between city $A$ and city $B$. $A$ and $B$ are distinct natural numbers at most $N$, and $C$ is a natural number at most $10000$. More than one road may join the same pair of cities.

Print the minimum total cost of conquering every city.

In the first example, city $3$, which is joined to city $1$, falls first. Conquering it costs $2$. After city $3$ falls, every road cost rises by $8$. The cities held are $1$ and $3$.

City $4$ is joined to city $3$, which is already held, so it can be conquered from city $3$ at the cost of the road between cities $3$ and $4$, which is now $1+8$. The cities held are $1$, $3$, and $4$.

City $2$ is also joined to city $3$, so it can be conquered too. Conquering it costs the road between cities $2$ and $3$, which is now $2+8+8$. Every city has now fallen.

The total is $2 + (1+8) + (2+8+8) = 29$.