import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	
	public static final int INF = 1000000000;
	
	private class MyScanner {
		public BufferedReader br;
		public StringTokenizer s;
		
		public MyScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		
		public String nextToken() {
			if (s == null || !s.hasMoreElements()) {
				try {
					s = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			
			return s.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(nextToken());
		}
	}
	
	private class MyPW {
		public PrintWriter pw;
		
		public MyPW(String s) {
			try {
				pw = new PrintWriter(new BufferedWriter(new FileWriter(s)));
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		
		public void writeResult(int[] dist) {
			for (int i = 2; i < dist.length; i++) {
				if (dist[i] == INF)
					pw.printf("0 ");
				else {
					pw.printf("%d ", dist[i]);
				}
			}
			
			pw.printf("\n");
			pw.close();
		}
	}
	
	private class Pair implements Comparable<Pair>{
		public int left, right;
		
		public Pair(int left, int right) {
			this.left = left;
			this.right = right;
		}

		@Override
		public int compareTo(Pair arg0) {
			if (left < arg0.left)
				return -1;
			
			if (left > arg0.left)
				return 1;
			
			return 0;
		}
	}
	
	public static void main(String[] args) {
		
		Main sol = new Main();
		MyScanner scanner = sol.new MyScanner("dijkstra.in");
		MyPW pw = sol.new MyPW("dijkstra.out");
		
		int n, m;
		
		n = scanner.nextInt();
		m = scanner.nextInt();
		
		int[] dist = new int[n+1];
		
		dist[1] = 0;
		
		for (int i = 2; i <= n; i++)
			dist[i] = INF;
		
		ArrayList<Pair>[] G = new ArrayList[n+1];
		
		for (int i = 1; i <= n; i++)
			G[i] = new ArrayList<Pair>();
		
		for (int i = 0; i < m; i++) {
			int a, b, c;
			a = scanner.nextInt();
			b = scanner.nextInt();
			c = scanner.nextInt();
			
			G[a].add(sol.new Pair(b, c));
		}
		
		TreeSet<Pair> set = new TreeSet<>();
		set.add(sol.new Pair(0, 1));
		
		while (!set.isEmpty()) {
			Pair p = set.first();
			
			set.remove(p);
			
			if (dist[p.right] != p.left)
				continue;
			
			for (Pair vec : G[p.right]) {
				if (p.left + vec.right < dist[vec.left]) {
					set.remove(sol.new Pair(dist[vec.left], vec.left));
					
					dist[vec.left]= p.left + vec.right;
					
					set.add(sol.new Pair(dist[vec.left], vec.left));
				}
			}
		}
		
		pw.writeResult(dist);
	}

}