Dijkstra's Shortest Path

Ravensmoor Couriers plans runs across a town. Each road joins two junctions and takes a known number of minutes to drive, the same in either direction. A rider starts at one junction, and the office wants the quickest time to every junction in town — including the ones no road reaches, which must be reported as such rather than left blank.

Task: Print the quickest travelling time from the start junction to each junction in turn.

Input

The first line holds two integers separated by a space: n, the number of junctions labelled 0 to n-1, and m, the number of roads. Each of the next m lines holds three integers u v w — a road between u and v taking w minutes, w at least 1. The last line holds the starting junction. m may be 0.

Output

One line holding n integers separated by single spaces: the quickest time to junction 0, then junction 1, and so on. A road may be driven in either direction. The start junction's own time is 0. Print -1 for any junction no run of roads reaches.

Example:

Input:
4 4
0 1 1
1 2 2
0 2 4
2 3 1
0

Output:
0 1 3 4