package dijsktra;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Dijsktra {
	FileInputStream input;
	FileOutputStream output;
	int n;
	int[][] A;
	int[] dist;
	
	public Dijsktra() {
		this(null, null);
	}
	
	public Dijsktra(String input, String output) {
		try {
			this.input = new FileInputStream(input);
			this.output = new FileOutputStream(output);
		}
		catch (IOException e) {
			System.err.println(e);
		}
	}
	
	public static void main(String[] argv) {
		System.out.println(System.getProperty("user.dir")+"/" + argv[0]);
		Dijsktra exec = new Dijsktra("dijkstra.in", "dijkstra.out");
		exec.read();
		exec.write(exec.dijsktra(1));
	}
	
	public int[] dijsktra(int root) {
		dist = new int[n+1];
		
		PriorityQueue<Integer> Q = new PriorityQueue<Integer>(n+1, 
			new Comparator<Integer>(){
			public int compare(Integer a, Integer b) {
				return dist[b] - dist[a];
			}
		});
		
		for (int i = 1; i <= n; i++) {
			dist[i] = Integer.MAX_VALUE;
			Q.add(i);
		}
		
		dist[root] = 0;
		
		while (!Q.isEmpty()) {
			int u = Q.peek();
			for (Integer x : Q) {
				if (dist[x] < dist[u]) 
					u = x;
			}
			Q.remove(u);
			
			for (int v = 1; v <= n; v++) {
				if (A[u][v] != Integer.MAX_VALUE) {
					if (dist[u] + A[u][v] < dist[v]) {
						dist[v] = dist[u] + A[u][v];
					}
				}
			}
		}
		disply();
		return dist;
	}
	
	public void disply() {
		
		for (int i = 2; i <= n; i++) {
			System.out.print((dist[i] == Integer.MAX_VALUE ? 0 : dist[i]) + " ");
		}
	}
	
	public String toString() {
	String res = "";
		for (int i = 2; i <= n; i++) {
			res += (dist[i] == Integer.MAX_VALUE ? 0 : dist[i]) + " ";
		}
		return res;
	}
	
	public void write(int dist[]) {
		try {
			output.write(toString().getBytes());
			output.flush();
			output.close();
		}
		catch (IOException e) {
			
		}
		finally {
			
		}
	}
	
	public void read() {
		Scanner scanner = null;
		try {
			scanner = new Scanner(input);
			n = scanner.nextInt();
			A = new int[n+1][n+1];
			int m = scanner.nextInt();
//			System.out.println(n + " " + m);
			for (int i = 0; i <= n; i++) 
				for (int j = 0; j <= n; j++) 
					A[i][j] = Integer.MAX_VALUE;
			
			for (int i = 0; i < m; i++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				int c = scanner.nextInt();
				
				A[x][y] = c;
			}
		}
		catch (Exception e) {
			System.err.println(e);
		}
		finally {
			try {
				scanner.close();
			}
			catch (Exception e) {
				System.err.println(e);
			}
		}
	}
}