Ceste

A country has $N$ cities and $M$ two-way roads. Driving along road $i$ takes $T_i$ minutes and costs $C_i$ kuna. Kuna is the currency of Croatia.

You start in city $1$. For a route, the total time is the sum of $T_i$ over the roads you drive along, and the total cost is the sum of $C_i$ over the same roads. The value of a route is its total time multiplied by its total cost.

For every city other than city $1$, find the smallest value among all routes from city $1$ to that city. If no such route exists, print $-1$.

The first line contains the number of cities $N$ ($1 \le N \le 2000$) and the number of roads $M$ ($1 \le M \le 2000$).

Each of the next $M$ lines contains four integers $A_i$, $B_i$, $T_i$, $C_i$ ($1 \le A_i, B_i \le N$, $1 \le T_i, C_i \le 2000$). They mean that a road connects city $A_i$ and city $B_i$, and driving along it takes $T_i$ minutes and costs $C_i$ kuna.

Two cities can be connected by more than one road. No road connects a city to itself.

Print $N - 1$ lines. On line $i$, print the smallest value among all routes from city $1$ to city $i + 1$. If the two cities are not connected, print $-1$.

Consider the second example.

To reach city $2$ you drive along road $1$. It takes $1$ minute and costs $7$ kuna, so the value is $7$.

To reach city $3$ you drive along road $2$. It takes $3$ minutes and costs $2$ kuna, so the value is $6$.

To reach city $4$ you drive along roads $2$, $4$ and $5$ in that order. Together they take $11$ minutes and cost $4$ kuna, so the value is $44$.