package dijsktra;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Dijsktra {
	private File input;
	private File output;
	int n;
	int[][] A;
	
	public Dijsktra() {
		this(null, null);
	}
	
	public Dijsktra(String input, String output) {
		this.input = new File(input);
		this.output = new File(output);
		if (!this.output.exists()) {
			try {
				this.output.createNewFile();
			}
			catch (IOException e) {
				System.err.println(e);
			}
		}
	}
	
	public static void main(String[] argv) {
		Dijsktra exec = new Dijsktra(argv[0], argv[1]);
		exec.read();
		exec.write(exec.dijsktra(1));
	}
	
	public void write(int dist[]) {
		FileWriter writer = null;
		
		try {
			writer = new FileWriter(output);
			
			for (int i = 2; i <= n; i++) {
				writer.write(dist[i] + " ");
			}
		}
		catch (IOException e) {
			
		}
		finally {
			try {
				writer.close();
			}
			catch (IOException e){
				
			}
		}
	}
	
	public int[] dijsktra(int root) {
		int[] dist = new int[n+1];
		PriorityQueue<Integer> Q = new PriorityQueue<Integer>(n+1, 
			new Comparator<Integer>(){
			public int compare(Integer a, Integer b) {
				return b - a;
			}
		});
		
		for (int i = 1; i <= n; i++) {
			dist[i] = Integer.MAX_VALUE;
		}
		
		dist[root] = 0;
		Q.add(root);
		
		while (!Q.isEmpty()) {
			int u = Q.remove();
			
			for (int v = 1; v <= n; v++) {
				if (A[u][v] != 0) {
					if (dist[u] + A[u][v] < dist[v] && dist[u] + A[u][v] > 0) {
						dist[v] = dist[u] + A[u][v];
						Q.add(v);
					}
				}
			}
		}
		
		for (int i = 2; i <= n; i++)
			System.out.print(dist[i] + " ");
		
		return dist;
	}
	
	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();
			
			for (int i = 0; i < m; i++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				int c = scanner.nextInt();
				
				A[x][y] = c;
			}
		}
		catch (FileNotFoundException e) {
			System.err.println(e);
		}
		finally {
			try {
				scanner.close();
			}
			catch (Exception e) {
				System.err.println(e);
			}
		}
	}
}