import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {
        BufferedReader in = new BufferedReader(new FileReader("dijkstra.in"));
        String temp[] = in.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);
        g = new ArrayList<Node>();
        for (int i = 0; i <= n; i++) {
            g.add(new Node());
        }
        vis = new int[n + 1];
        dist = new int[n + 1];
        for (int i = 0; i < m; i++) {
            temp = in.readLine().split(" ");
            int x = Integer.parseInt(temp[0]);
            int y = Integer.parseInt(temp[1]);
            int c = Integer.parseInt(temp[2]);
            g.get(x).n = x;
            g.get(x).ngh.add(new Pair(y, c));
            if (x == 1) {
                dist[y] = c;
            } else {
                dist[y] = Integer.MAX_VALUE;
            }
        }
        dijkstra(1);
        PrintWriter out = new PrintWriter("dijkstra.out");
        for(int i = 2; i < dist.length ; i++){
            out.print(dist[i] + " ");
        }
        out.close();
    }
    static List<Node> g;
    static int vis[];
    static int dist[];

    private static void dijkstra(int src) {
        vis[src] = 1;
        dist[src] = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(
                g.size(), new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        int d1 = dist[o1];
                        int d2 = dist[o2];
                        return d1 > d2 ? 1 : -1;
                    }
                });
        for (int i = 1; i < g.size(); i++) {
            pq.add(i);
        }
        while (!pq.isEmpty()) {
            int n = pq.poll();
            vis[n] = 1;
            for (Pair p : g.get(n).ngh) {
                if (vis[p.n] != 1) {
                    if (dist[p.n] > dist[n] + p.c) {
                        dist[p.n] = dist[n] + p.c;
                    }
                }
            }
        }
    }

    static class Pair {

        int n;
        int c;

        public Pair(int n, int c) {
            this.n = n;
            this.c = c;
        }

        @Override
        public String toString() {
            return "Pair{" + "n=" + n + ", c=" + c + '}';
        }
    }

    static class Node {

        int n;
        List<Pair> ngh;

        public Node(int n) {
            this.n = n;
            this.ngh = new ArrayList<Pair>();
        }

        public Node() {
            this.ngh = new ArrayList<Pair>();
        }

        @Override
        public String toString() {
            return "{n=" + n + "} " + ngh;
        }

    }
}