Minimizing Combined Video Duration on Routes

Sky does not want to waste any footage. He plans to concatenate two videos and post the result on a popular video platform. Since short videos are more popular these days, Sky wishes to minimize the total duration of the two videos. To decide on travel destinations and routes, you are required to calculate, for each destination \(k\), the minimal total duration of the two videos among all possible routes from city \(1\) to city \(k\).

The cities and roads are modeled as a directed graph with \(n\) cities and \(m\) roads. Each road from city \(u\) to city \(v\) is associated with two non-negative durations \(a\) and \(b\); when traveling that road the total time added is \(a+b\). If a city cannot be reached from city \(1\), output \(-1\) for that city.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of cities and the number of roads, respectively.

Each of the next \(m\) lines contains four integers \(u\), \(v\), \(a\), and \(b\), indicating there is a road from city \(u\) to city \(v\) with durations \(a\) and \(b\) for the two videos.

outputFormat

Output \(n\) integers separated by spaces. The \(k\)th integer represents the minimal total duration (i.e. \(a+b\)) from city \(1\) to city \(k\). If a city is unreachable from city \(1\), output \(-1\) for that city.

sample

3 3
1 2 1 2
2 3 1 1
1 3 4 0

0 3 4