410553: GYM104049 E Steel Customs

You are the president of the micronation of Steelistan and as a result, you are responsible for handling the monthly exports of steel to other countries.

There are $$$N$$$ countries in the world and $$$M$$$ border crossings between pairs of countries that share a border (countries may share a border but not have a crossing due to geographical reasons). Every country has a distinct code number between $$$1$$$ and $$$N$$$, and Steelistan is denoted as country $$$1$$$. Each border crossing is between two different countries $$$A_i$$$ and $$$B_i$$$ and requires a customs fee $$$C_i$$$ to cross in either direction. Although shipping free within a country, exported steel may need to pass through several countries and thus several border crossings.

Understandably, these customs fees add up over time, so all the countries made a trade agreement to reduce costs for everyone: instead of paying the full sum of customs fees over multiple border crossings, a shipment is allowed to instead pay a separate fee $$$F$$$ at a single border crossing (but must still pay the full amount at all others). Steelistan is conveniently allowed to to exercise this right once a month for one steel shipment to each other country.

With this trade agreement in place, can you determine the minimal cost to export steel to every other nation?

The first line of input contains three integers $$$N$$$ ($$$2 \leq N \leq 10^5$$$), $$$M$$$ ($$$1 \leq M \leq 10^5$$$), and $$$F$$$ ($$$1 \leq F \leq 10^5$$$), representing the number of countries in the world, border crossings, and fixed cost of a border crossing under the trade agreement. The next $$$M$$$ lines of input each have three integers $$$A_i$$$ ($$$1 \leq A_i \leq N$$$, $$$A_i \neq B_i$$$), $$$B_i$$$ ($$$1 \leq B_i \leq N$$$, $$$B_i \neq A_i$$$), and $$$C_i$$$ ($$$1 \leq C_i \leq 10^5$$$), which describe a single border crossing. It is possible for there to be multiple border crossings between the same pair of countries.

Output $$$N - 1$$$ lines with a single integer each, the $$$i$$$-th of which represents the minimal cost to export from Steelistan to nation with code number $$$i+1$$$ (or $$$-1$$$, if it is not possible to reach that nation from Steelistan).

4 4 2
1 2 3
2 4 2
4 3 8
1 3 1

2
1
3