//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;
    ArrayList<Integer>  sp;
    PriorityQueue<qNode> pq;
    ArrayList<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);
        sp = new ArrayList<>(n);
        inQueue = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            ArrayList<Node> nodelist = new ArrayList<>();
            graph.add(nodelist);
            inQueue.add(false);
            sp.add(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.get(i) + " ");
        }
        writer.println();
        writer.close();
    }

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

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

        for(int i = 0; i < n; i++) {
            if(sp.get(i) == Integer.MAX_VALUE) {
                sp.set(i, 0);
            }
        }
    }

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