package yeet;
import java.io.*;
import java.util.*;

class Pear implements Comparable<Pear> {
	int x;
	int y;
	
	Pear(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public int compareTo(Pear o) {
		// TODO Auto-generated method stub
		return this.y-o.y;
	}
	
}

class Pair implements Comparator<Pair>{
	int x;
	int y;
	
	Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public int compare(Pair o1, Pair o2) {
		// TODO Auto-generated method stub
		if (o1.y < o2.y) {
			return -1;
		}
		if (o1.y > o2.y) {
			return 1;
		}
		return 0;
	}
}

public class Main {
	private static int n;
	private static int m;
	
	public static void main(String[] args) throws FileNotFoundException{
		File f = new File("dijkstra.in");
		PrintStream out = new PrintStream("dijkstra.out");
		Scanner console = new Scanner(f);
		
		n = console.nextInt();
		m = console.nextInt();
		
		ArrayList<Pair>[] g = new ArrayList[n+1];
		for (int i = 1; i <= n; i++) {
			g[i] = new ArrayList<Pair>();
		}
		
		for (int i = 1; i <= m; i++) {
			int x = console.nextInt();
			int y = console.nextInt();
			int c = console.nextInt();
			Pair p = new Pair(y, c);
			g[x].add(p);
		}
			
		int[] d = dijkstra(g);	
		for (int i = 2; i <= n; i++) {
			out.print(d[i] + " ");
		}	
	}
	
	public static int[] bellman(ArrayList<Pair>[] g) {
		int[] d = new int[n+1];
		for (int i = 1; i <= n; i++) {
			d[i] = 2000000000;
		}
		d[1] = 0;
		for (int i = 1; i < n; i++) {
			// for all edges in E
			for (int j = 1; j <= n; j++) {
				for (Pair p : g[j]) {
					int v = p.x;
					int u = j;
					int cost = p.y;
					d[v] = Math.min(d[v], d[u] + cost);
				}
			}
		}
		
		// try again to see if we find negative cycle
		
		return d;
	}
	
	public static int[] dijkstra(ArrayList<Pair>[] g) {
		boolean[] viz = new boolean[n+1];
		int[] d = new int[n+1];
		for (int i = 1; i <= n; i++) {
			d[i] = 2000000000;
		}
		d[1] = 0;
		PriorityQueue<Pear> heap = new PriorityQueue<>();
		Pear s = new Pear(1, 0);
		heap.add(s);
		
		while (!heap.isEmpty()) {
			Pear p = heap.poll();
			if (viz[p.x]) {
				continue;
			}
			
			viz[p.x] = true;
			for (Pair i : g[p.x]) {
				int vec = i.x;
				int cost = i.y;
				if(!viz[vec] && d[vec] > d[p.x]+cost) {
					d[vec] = d[p.x] + cost;
					heap.add(new Pear(vec, d[vec]));
				}
			}
		}
		
		return d;
	}
}