package com.company;

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

public class Main {


    public static void main(String[] args) throws IOException {
        new Main().dijkstra();
    }

    class Edge {
        int v;
        int cost;

        public Edge(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    List<List<Edge>> a;
    final int N = 50000;


    int d[] = new int[N];
    boolean vis[] = new boolean[N];

    int INF = 251000;

    public void dijkstra() throws IOException {
//        File f = new File("dijkstra.in");
//        try {
//            f.createNewFile();
//        } catch (IOException e) {
//            e.printStackTrace();
//        }

        Scanner scanner = new Scanner(new File("dijkstra.in"));

        int[] tall = new int[100];

        int n = scanner.nextInt();
        int m = scanner.nextInt();


        a = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; ++i) {
            a.add(null);
            d[i] = INF;
            vis[i] = false;
        }
        vis[1] = true;

        for (int i = 0; i < m; ++i) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int cost = scanner.nextInt();

            if (a.get(u) == null)
                a.set(u, new LinkedList<>());
            a.get(u).add(new Edge(v, cost));
        }

        final int sourceNode = 1;
        for (Edge edge : a.get(sourceNode)) {
            d[edge.v] = edge.cost;
        }


        while (true) {
            int dMin = INF;
            int iMin = -1;
            for (int i = 1; i < n; ++i)
                if (!vis[i]) {
                    if (d[i] < dMin) {
                        dMin = d[i];
                        iMin = i;
                    }
                }

            if (dMin >= INF)
                break; //TODO!!! crash...

            vis[iMin] = true;

            for (Edge edge : a.get(iMin)) {
                d[edge.v] = Math.min(dMin + edge.cost, d[edge.v]);
            }
        }

        try (BufferedWriter bw = new BufferedWriter(new FileWriter("dijkstra.out"))) {
            for (int i = 2; i <= n; ++i) {
                if (d[i] >= INF)
                    d[i] = 0;
                bw.write(d[i] + " ");
            }
            bw.write("\n");
        }
    }
}