//package drum_minim;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Dijkstra {
	
	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public MyScanner(String file) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(file)));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine(){
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
	
	static int[] distance;
	
	private static class NodeComparator implements Comparator<NodeT<Integer>> {
        public int compare(NodeT<Integer> arg0, NodeT<Integer> arg1) {
            int dist1 = distance[arg0.id()];
            int dist2 = distance[arg1.id()];

            return dist1 > dist2 ? 1 : -1;
        }
    }
	
	private static void dijkstra(NodeT<Integer> source, GraphT<Integer, Integer> g) {
		for (int i = 0; i < g.size(); i++) 
            distance[i] =  Integer.MAX_VALUE;
		
		PriorityQueue<NodeT<Integer>> pq = new PriorityQueue<>(g.size(), new NodeComparator());

        distance[source.id()] = 0;
        pq.add(source);
        
        while (!pq.isEmpty()) {
        	NodeT<Integer> nod = pq.poll();
        	nod.visit();
        	for (PairT<NodeT<Integer>, Integer> pair : g.adjList(nod)) {
        		if (!pair.first().isVisited() && (distance[pair.first().id()] > distance[nod.id()] + pair.second())) {
        			pq.remove(pair.first());
        			distance[pair.first().id()] = distance[nod.id()] + pair.second();
        			pair.first().setParent(nod);
        			pq.add(pair.first());
        		}
        	}
        }
        
//        for (int i = 0; i < g.size(); i++) 
//        	System.out.println(i + " " + distance[i]);
	}
	public static void main(String[] args) throws IOException {
		GraphT<Integer, Integer> g = new GraphT<Integer, Integer>();
//		for (int i = 0; i < 5; i++)
//			g.insertNode(new NodeT<Integer>(i));
//		
//		g.insertEdge(g.getNode(0), g.getNode(1), 1);
//		g.insertEdge(g.getNode(0), g.getNode(3), 2);
//		g.insertEdge(g.getNode(3), g.getNode(2), 4);
//		g.insertEdge(g.getNode(1), g.getNode(2), 2);
//		g.insertEdge(g.getNode(3), g.getNode(4), 3);
//		g.insertEdge(g.getNode(2), g.getNode(4), 6);
		
		MyScanner sc = new MyScanner("dijkstra.in");
		BufferedWriter writer = new BufferedWriter(new FileWriter("dijkstra.out"));
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		for (int i = 0; i < N; i++)
			g.insertNode(new NodeT<Integer>(i));
		for (int i = 0; i < M; i++) {
			int node1 = sc.nextInt() - 1;
			int node2 = sc.nextInt() - 1;
			int cost = sc.nextInt();
			g.insertEdge(g.getNode(node1), g.getNode(node2), cost);
		}
		
		distance = new int[g.size()];
		
		dijkstra(g.getNode(0), g);
		
		for (int i = 1; i < g.size(); i++)
			writer.write(distance[i] + " ");
		writer.close();
	}
}