//package random;

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

public class Main {

    public static void main(String[] args) throws IOException {
        Graph graph = new Graph("dijkstra.in");
        ArrayList<Integer> a = graph.djikstra(1);

        FileWriter fileWriter = new FileWriter("dijkstra.out");
        PrintWriter printWriter = new PrintWriter(fileWriter);
        for (int i = 2; i < a.size(); i++) {
            printWriter.print((a.get(i) == Integer.MAX_VALUE ? 0 : a.get(i))+" ");
        }

        printWriter.close();
        fileWriter.close();
    }
}

class Graph {
    public Graph(final String filename) throws FileNotFoundException {
        File file = new File(filename);
        Scanner scanner = new Scanner(file);
        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();
        adj_list = new ArrayList<LinkedList<P>>();
        for (int i = 0; i <= n; i++) {
            adj_list.add(new LinkedList<P>());
        }

        int f, g, h;
        for (int i = 0; i < m; i++) {
            f = scanner.nextInt();
            g = scanner.nextInt();
            h = scanner.nextInt();
            adj_list.get(f).add(new P(g, h));
        }

        scanner.close();
    }

    public ArrayList<Integer> djikstra(int k) {
        ArrayList<Integer> dist = new ArrayList<>(Collections.nCopies(adj_list.size(), Integer.MAX_VALUE));
        PriorityQueue<P> pq = new PriorityQueue<>(adj_list.size());
        pq.add(new P(0, k));
        dist.set(k, 0);

        P top;
        while (!pq.isEmpty()) {
            top = pq.poll();

            if (top.getKey() == dist.get(top.getValue())) {
                for (P e : adj_list.get(top.getValue())) {
                    if (dist.get(e.getKey()) > dist.get(top.getValue()) + e.getValue()) {
                        dist.set(e.getKey(), dist.get(top.getValue()) + e.getValue());
                        pq.add(new P(dist.get(e.getKey()), e.getKey()));
                    }
                }
            }
        }
        return dist;
    }

    private class P implements Comparable<P> {
        private int key;
        private int value;

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        public P(int key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(P other) {
            return (Integer.compare(this.getKey(), other.getKey()));
        }
    }

    private ArrayList<LinkedList<P>> adj_list;
};