Shortest Travel Time from Warehouse

You are given an undirected graph with N nodes, numbered from 0 to N−1, and M roads. Each road is represented by a triplet (u, v, w), which indicates that there is a road between nodes u and v with a travel time of w. The central warehouse is located at node 0.

Your task is to compute the shortest travel time from the warehouse to every other node. If a node is unreachable, output INF for that node.

The shortest path update follows the formula: $$d[v] = \min(d[v],\; d[u] + w)$$ where \(d[u]\) is the current shortest distance to node \(u\) and \(w\) is the travel time from \(u\) to \(v\).

inputFormat

The input is read from standard input in the following format:

• The first line contains two integers N and M — the number of nodes and the number of roads.
• The following M lines each contain three integers u, v, and w indicating that there is a road between node u and node v with travel time w.

outputFormat

Output a single line containing N values separated by spaces. The i-th value is the shortest travel time from node 0 to node i. If node i is unreachable, print INF instead of its travel time.

5
7
0 1 10
0 2 3
1 2 1
1 3 2
2 3 8
2 4 2
3 4 7

0 4 3 6 5