Cows Drive

The cows decided to just drive instead of flying. In the country where they live, there are $V$ cities and $E$ bidirectional highways connecting pairs of cities. The cows live in city $1$, where Sunlin Internet High School is. Oh, and here is a tip: in the middle of every highway there is a rest stop that sells tonkatsu.

Vacation season has arrived and the cows set off on a trip. As you know, Bessie the cow wants to travel to another city. Bessie will ride the highways appropriately to reach her destination. Choose the route well and find the minimum time needed to travel from city $1$ to the city Bessie will visit. Oh, which city she will visit is a secret. So for each city from $2$ to $N$, find the minimum time needed to travel from city $1$ to that city.

... But Bessie suddenly feels empty. She has learned that this problem is far too easy to solve with Dijkstra's algorithm, and she has also realized her own desire to eat the tonkatsu sold at the highway rest stops. Bessie surveyed every tonkatsu at every highway and recorded a numeric value for its taste. On the route she takes for her vacation, Bessie will stop at exactly one of the rest stops and buy tonkatsu to eat. For each city from $2$ to $N$ that Bessie can visit, choose the route and the rest stop to visit well, and find the minimum value of the time needed to travel from city $1$ to that city minus the taste of the tonkatsu she eats after appropriately stopping at one rest stop along the way. Of course, the time spent eating tonkatsu is not included in the travel time.

The first line gives the number of cities in the country, $V$, and the number of highways, $E$.

From the second line, $E$ lines give information about each highway. Each line gives the two cities $x$ and $y$ that the highway connects, the time $t$ needed to travel from $x$ to $y$, and the value $k$ representing the taste of the tonkatsu sold at the rest stop, in that order, separated by spaces.

There are no two or more highways connecting the same pair of cities. All cities are connected directly or indirectly through the highways.

Print $V-1$ integers in total, one per line. The $i$-th integer printed is the minimum value of the time needed to travel from city $1$ to city $i+1$ minus the taste of the tonkatsu eaten along the way.

• $1 \le V \le 100,000$
• $1 \le E \le 100,000$
• $1 \le x \neq y \le V$
• $1 \le t \le 20,000$
• $1 \le k \le 1,000,000,000$