import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
	 static ArrayList<Pair<Integer, Integer>> [] adj;
	 static int[] dist;
	 static boolean[] set;

	 
	public static void main(String[] args) throws IOException {
		 BufferedReader bf = new BufferedReader(new FileReader("dijkstra.in"));
		 //PrintStream out = new PrintStream();
		 OutputStream out = new BufferedOutputStream ( new FileOutputStream("dijkstra.out") );
	     String tmp[] = bf.readLine().split(" ");
	     int n = Integer.parseInt(tmp[0]);
	     int m = Integer.parseInt(tmp[1]);
	   
	     Comparator <Pair<Integer, Integer>> c =new Comparator<Pair<Integer, Integer>>() {

			@Override
			public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
				return o1.y - o2.y;
			}
		};
		 PriorityQueue<Pair<Integer, Integer> >  q = new PriorityQueue<>(1, c);
		 dist = new int[n+1];
		 adj = new ArrayList[n+1];
		 set = new boolean[n+1];
		 for(int i=1; i<=n; i++) {
			 set[i] = false;
			 adj[i] = new ArrayList<Pair<Integer, Integer> >();
			 dist[i] = Integer.MAX_VALUE;
		 }
		 dist[1] = 0;
		int x,y,d;
	     for (int i = 0; i < m; i++) {
           tmp = bf.readLine().split(" ");
            x = Integer.parseInt(tmp[0]);
            y = Integer.parseInt(tmp[1]);
            d = Integer.parseInt(tmp[2]);
           adj[x].add(new Pair<Integer, Integer>(y, d));
           if (x == 1) {
        	   q.add(new Pair<Integer, Integer>(y, d));
        	   dist[y] = d;
           }
        	   
	     }
	     
        set[1] = true;
	    while (q.isEmpty() == false){
	    	Pair <Integer, Integer> u = q.poll();
	    
	    	set[u.x] = true;
	    	for (Pair<Integer, Integer> v : adj[u.x]){
	    		if ((!set[v.x]) && dist[u.x] < Integer.MAX_VALUE && 
	    				dist[u.x] + v.y < Integer.MAX_VALUE && (dist[v.x] > dist[u.x] + v.y)){
	    			dist[v.x] = dist[u.x] + v.y;
	    			q.add(new Pair<Integer, Integer>(v.x, dist[v.x]));	
	    		}
	    	}
	    }
	    for (int i = 2 ;i <= n;i++){
	    	if (dist[i]==Integer.MAX_VALUE)
	    		out.write(("0 ").getBytes());
	    	else
	    		out.write((dist[i]+" ").getBytes());
	    }
	    out.write(("\n").getBytes());
		 out.flush();
		 out.close();
		 bf.close();
		 
	}
}

	class Pair <A,B>{
		A x;
		B y;
		public Pair(A x, B y) {
			super();
			this.x = x;
			this.y = y;
		}
	}