Score : 500 points
There are N cities numbered 1 to N, connected by M railroads.
You are now at City 1, with 10^{100} gold coins and S silver coins in your pocket.
The i-th railroad connects City U_i and City V_i bidirectionally, and a one-way trip costs A_i silver coins and takes B_i minutes. You cannot use gold coins to pay the fare.
There is an exchange counter in each city. At the exchange counter in City i, you can get C_i silver coins for 1 gold coin. The transaction takes D_i minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.
For each t=2, ..., N, find the minimum time needed to travel from City 1 to City t. You can ignore the time spent waiting for trains.
Input is given from Standard Input in the following format:
N M S U_1 V_1 A_1 B_1 : U_M V_M A_M B_M C_1 D_1 : C_N D_N
For each t=2, ..., N in this order, print a line containing the minimum time needed to travel from City 1 to City t.
3 2 1 1 2 1 2 1 3 2 4 1 11 1 2 2 5
2 14
The railway network in this input is shown in the figure below.
In this figure, each city is labeled as follows:
Similarly, each railroad is labeled as follows:
You can travel from City 1 to City 2 in 2 minutes, as follows:
You can travel from City 1 to City 3 in 14 minutes, as follows:
4 4 1 1 2 1 5 1 3 4 4 2 4 2 2 3 4 1 1 3 1 3 1 5 2 6 4
5 5 7
The railway network in this input is shown in the figure below:
You can travel from City 1 to City 4 in 7 minutes, as follows:
6 5 1 1 2 1 1 1 3 2 1 2 4 5 1 3 5 11 1 1 6 50 1 1 10000 1 3000 1 700 1 100 1 1 100 1
1 9003 14606 16510 16576
The railway network in this input is shown in the figure below:
You can travel from City 1 to City 6 in 16576 minutes, as follows:
4 6 1000000000 1 2 50 1 1 3 50 5 1 4 50 7 2 3 50 2 2 4 50 4 3 4 50 3 10 2 4 4 5 5 7 7
1 3 5
The railway network in this input is shown in the figure below:
2 1 0 1 2 1 1 1 1000000000 1 1
1000000001
The railway network in this input is shown in the figure below:
You can travel from City 1 to City 2 in 1000000001 minutes, as follows: