Olympic Airlines#4975
The Emperor of Olympia has decided to connect cities within the empire using air transport. The court programmer has been assigned the task of developing a program named OlympBuild to streamline the creation of a flight map. This program must handle two types of operations, each involving three parameters: , , and :
Establish a new flight from city to city , with a duration of minutes.
For all flights originating from city , let flight number terminate at city v_i and take t_i minutes. For each such , create a flight from city to city v_i, with a duration of t_i + C minutes.
After executing all operations, the program must determine the shortest time required to fly from the capital to each city, potentially involving transfers at other cities. It is assumed that boarding, disembarking, and waiting times at airports are zero.
There can be multiple flights between two cities, each with different durations. Flights may also start and end in the same city. All flights are one-way, meaning a direct flight from city to city does not imply a direct flight from city to city .
Write a program that, given a sequence of operations as described above, executed by the OlympBuild program, finds the shortest time required to fly from the capital to each city, except the capital itself.
The first line contains two integers and (2 \le N \le 10^5, 1 \le M \le 10^5)—the number of cities in the Olympia empire and the number of operations performed by the OlympBuild program. Each of the following lines contains details of an operation. The first number in the line is if the operation is of the first type, and if it is of the second type. This is followed by three integers , , and (1 \le A \le N, 1 \le B \le N, -10^8 \le C \le 10^8), as described above. Cities are numbered from to , with the capital being city . It is guaranteed that the flight time for each flight will be strictly positive.
Output N - 1 lines. In the -th line, provide the shortest time in minutes to fly from the capital to the city numbered i + 1. If a city is unreachable, output the number for that city.
Example 1