package graph;

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Dijkstra_ElogV implements Runnable {

	class Pair implements Comparable<Pair>{
		int number;
		double d;


		public int compareTo(Pair that) {
			if(d < that.d) return -1;
			if(d > that.d) return 1;
			return 0;
		}
	}

	class Edge {
		int v1;
		int v2;
		int w;

		Edge(int v1, int v2, int w) {
			this.v1 = v1;
			this.v2 = v2;
			this.w = w;
		}
	}

	int n;
	int m;
	int[] head;
	Edge[] value;
	int[] next;
	Pair[] d;

	PriorityQueue<Pair> q =  new PriorityQueue<Pair>();

	void relax(Edge e) {
		if(d[e.v1].d + e.w < d[e.v2].d) {

			q.remove(d[e.v2]);

			d[e.v2].d = d[e.v1].d + e.w;

			q.add(d[e.v2]);


		}
	}

	void dijkstra(int v) {

		d[v].d = 0;

		for(int i = 1; i <= n; i++) q.add(d[i]);

		while(!q.isEmpty()) {
			Pair u = q.poll();
			for(int i = head[u.number]; i != -1; i = next[i]) {
				relax(value[i]);
			}
		}

	}

	public void run() {
		try {
			BufferedReader in = new BufferedReader(new FileReader("input.txt"));
			PrintWriter out = new PrintWriter("output.txt");
			StringTokenizer st = new StringTokenizer(in.readLine());

			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			head = new int[n + 1];
			value = new Edge[m];
			next = new int[m];
			d = new Pair[n + 1];

			Arrays.fill(head, -1);

			for(int i = 1; i <= n; i++) {
				d[i] = new Pair();;
				d[i].number = i;
				d[i].d = Double.POSITIVE_INFINITY;
			}

			int t1;
			int t2;

			for(int i = 0; i < m; i++) {
				st = new StringTokenizer(in.readLine());
				t1 = Integer.parseInt(st.nextToken());
				t2 = Integer.parseInt(st.nextToken());

				value[i] = new Edge(t1, t2, Integer.parseInt(st.nextToken()));
				next[i] = head[t1];
				head[t1] = i;
			}

			dijkstra(1);

			for(int i = 1; i <= n; i++) {
				if(d[i].d == Double.POSITIVE_INFINITY) {
					out.print("inf ");
					continue;
				}
				out.print((int) d[i].d + " ");
			}

			in.close();
			out.close();
		} catch(IOException e) {}
	}

	public static void main(String[] args) {
		new Thread(new Dijkstra_ElogV()).start();
	}
}