Taco Relay Station Communication

In this problem, you are given a directed weighted graph representing a network of relay stations. The graph consists of N stations and E directed edges. Each edge has an associated time cost. Your task is to compute the minimum time required to send a message from station 1 to every other station using Dijkstra's algorithm.

Formally, given a directed graph (G=(V,E)) with (V={1,2,\dots,N}) and each edge ((u,v)) with a weight (w), find the shortest path distances (d(1,i)) for all (i\in {1,2,\dots,N}). If a station is unreachable from station 1, output (\infty) (or simply print the string "inf").

inputFormat

The first line of input contains two integers, (N) and (E), representing the number of stations and the number of directed edges, respectively. Each of the following (E) lines contains three integers (u), (v), and (w) indicating that there is a directed edge from station (u) to station (v) with a time cost of (w).

outputFormat

Print a single line containing (N) space-separated values. The (i)-th value represents the minimum time required to send a message from station 1 to station (i). For station 1, the value should be 0. For any station that is unreachable, print either (\infty) or the string "inf".## sample

6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
6 5 9
4 5 6

0 7 9 20 20 11