Shortest Paths in an Undirected Graph

You are given a weighted undirected graph with n vertices and m edges. Your task is to compute the shortest paths from a given starting vertex s to all other vertices using Dijkstra's algorithm. If a vertex is not reachable from s, output INF for that vertex.

The graph is provided as a list of edges. Each edge includes two endpoints and a weight. Note that there can be multiple ways to reach a vertex; you must output the minimum distance.

Example:

Input:
5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
1
Output:
2 3 7 6

</p>

In the above example, the shortest distances from vertex 1 are: 2 (to 2), 3 (to 3), 7 (to 4), and 6 (to 5).

Note: When reading the input from standard input (stdin), the first line contains two integers n and m. The following m lines contain three integers each representing an edge (u, v, w). Finally, a line with the starting vertex s is provided.

inputFormat

The first line contains two space-separated integers n and m, where n is the number of vertices and m is the number of edges.

The next m lines each contain three integers u, v, and w, representing an undirected edge between vertices u and v with weight w.

The last line contains a single integer s, the starting vertex.

outputFormat

Output a single line containing n - 1 space-separated values, where each value is the minimum distance from s to vertex i (for all vertices i from 1 to n excluding s). If a vertex is not reachable, output INF in its place.

## sample

5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
1

2 3 7 6