//package com.infoarena;

import java.io.*;
import java.util.*;


public class Main {
    int m, n;

    class qNode implements Comparable<qNode> {
        int node;
        int dv;

        qNode(int node, int dv) {
            this.node = node;
            this.dv = dv;
        }

        public int compareTo(qNode o) {
            return this.dv - o.dv;
        }
    }

    class Node {
        int node;
        int cost;

        Node(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }
    }

    ArrayList<ArrayList<Node>> graph;
    int[] sp;
    PriorityQueue<qNode> pq;
    boolean[] inQueue;

    void readInput() throws Exception
    {
        String inputFile = "dijkstra.in";
        Scanner s = new Scanner(new FileInputStream(inputFile));

        n = s.nextInt();
        m = s.nextInt();

        graph = new ArrayList<>(n);
        inQueue = new boolean[n];
        sp = new int[n];
        for (int i = 0; i < n; i++) {
            ArrayList<Node> nodelist = new ArrayList<>(m);
            graph.add(nodelist);
            inQueue[i] = false;
            sp[i] = Integer.MAX_VALUE;
        }
        pq = new PriorityQueue<>(n);

        for(int i = 0; i < m; i++) {
            ArrayList<Node> nodes = graph.get(s.nextInt() - 1);
            Node n = new Node(s.nextInt() - 1, s.nextInt());
            nodes.add(n);
        }
    }

    void writeOutput() throws Exception
    {
        String outputFile = "dijkstra.out";
        PrintWriter writer = new PrintWriter(outputFile);

        for(int i = 1; i < n; i++) {
            writer.print(sp[i] + " ");
        }
        writer.println();
        writer.close();
    }

    void execute()
    {
        pq.add(new qNode(0, 0));
        inQueue[0] = true;
        sp[0] = 0;

        while (!pq.isEmpty()) {
            qNode qn = pq.remove();
            inQueue[qn.node] = false;
            for (Node n : graph.get(qn.node)) {
                int dist_new = sp[qn.node] + n.cost;
                if(sp[n.node] >= dist_new) {
                    qNode qnn = new qNode(n.node, dist_new);
                    sp[n.node] = dist_new;
                    if(!inQueue[qnn.node]) {
                        pq.add(qnn);
                        inQueue[qn.node] = true;
                    }
                }
            }
        }

        for(int i = 0; i < n; i++) {
            if(sp[i] == Integer.MAX_VALUE) {
                sp[i]=0;
            }
        }
    }

    public static void main(String[] args) throws Exception
    {
        Main main = new Main();
        main.readInput();
        main.execute();
        main.writeOutput();
    }
}