Minimize Product of Time and Cost

There is a country with N cities and M bidirectional roads. Driving on road i takes \(T_i\) minutes and costs \(C_i\) kunas (Croatian currency). Starting from city 1, you wish to reach every other city such that the product of the total time and the total cost is minimized. In other words, if a path uses roads with total time \(T_{total}\) and total cost \(C_{total}\), you want to minimize \(T_{total} \times C_{total}\). Output the minimal product for each city (except city 1) or -1 if the city is unreachable from city 1.

Note: Roads are bidirectional, and you may use any road multiple times if needed (although that might not be optimal). Both \(T_i\) and \(C_i\) are positive integers.

inputFormat

The first line contains two integers \(N\) and \(M\) -- the number of cities and roads respectively.

Each of the next \(M\) lines contains four integers \(u\), \(v\), \(T_i\), and \(C_i\) representing a bidirectional road between cities \(u\) and \(v\) that takes \(T_i\) minutes to travel and costs \(C_i\) kunas.

outputFormat

Output \(N-1\) integers separated by spaces. The \(i\)th integer (starting from city 2) should be the minimal value of \(T_{total} \times C_{total}\) required to reach that city from city 1, or -1 if it is not possible to reach that city.

sample

4 4
1 2 1 7
3 2 3 2
1 4 6 1
2 4 5 1

7 36 6