There's a country with cities and
bidirectional roads. Driving on road
takes
minutes,
and costs
kunas (Croatian currency).
To make the arrival to the holiday destination as pleasant as possible, you want to make it
as fast and as cheap as possible. More specifically, you are in city and want to minimize
the product of total money spent and total time spent (overall, with all roads you drove on) in
getting to a city from city
. For each city (except city
), output the required minimal product
or
if city
and that city aren't connected.
Input Specification
The first line of input contains numbers
, the number of cities, and
,
the number of roads.
Each of the following lines contains four numbers,
that denote there is a road connecting cities
and
, that it takes
minutes to drive
on it, and it costs
kunas.
It is possible that multiple roads exist between two cities, but there will never be a road that
connects a city with itself.
Output Specification
You must output lines. In the
line, output the required minimal product in order to get
to city
, or
if cities
and
aren't connected.
Scoring
In test cases worth of total points, it will hold
.
Sample Input 1
4 4
1 2 2 4
3 4 4 1
4 2 1 1
1 3 3 1
Sample Output 1
8
3
14
Sample Input 2
4 5
1 2 1 7
3 1 3 2
2 4 5 2
2 3 1 1
2 4 7 1
Sample Output 2
7
6
44
Explanation for Sample Output 2
In order to get to city , you need to drive on road
, for that it takes
minute and
kunas, so the
required product is
.
In order to get to city , you need to drive on road
, for that it takes
minutes and
kunas, so the
required product is
.
In order to get to city , you need to drive on roads
in that order, and for that it takes a total of
minutes and
kunas, so the required product is
.
Sample Input 3
3 2
1 2 2 5
2 1 3 3
Sample Output 3
9
-1
Comments
Since the original data were weak, an additional test case was added, and all submissions were rejudged.