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;
        }

        public boolean equals(qNode o) {
            return this.node == o.node;
        }
    }

    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;

    void readInput() throws Exception
    {
        String inputFile = this.getClass().getSimpleName() + ".in";
        Scanner s = new Scanner(new File(inputFile));

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

        graph = new ArrayList<>(n);
        sp = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            ArrayList<Node> nodelist = new ArrayList<>();
            graph.add(nodelist);
            sp.add(i, 2000);
        }
        pq = new PriorityQueue<>();

        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 = this.getClass().getSimpleName() + ".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));
        sp.set(0, 0);

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

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

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