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

public class Main {
    static int n, m;
    static ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
    static long[] distante;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("dijkstra.in"));
        PrintWriter pw = new PrintWriter(new FileWriter("dijkstra.out"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        distante = new long[n + 1];
        Arrays.fill(distante, Long.MAX_VALUE);
        distante[1] = 0;

        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int lungime = Integer.parseInt(st.nextToken());
            graph.get(from).add(new int[]{to, lungime});
        }

        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.add(new long[]{0, 1});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long d = current[0];
            int nod = (int) current[1];

            if (d > distante[nod]) continue;

            for (int[] vecin : graph.get(nod)) {
                if (distante[nod] + vecin[1] < distante[vecin[0]]) {
                    distante[vecin[0]] = distante[nod] + vecin[1];
                    pq.add(new long[]{distante[vecin[0]], vecin[0]});
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            if (distante[i] == Long.MAX_VALUE)
                sb.append(0);
            else
                sb.append(distante[i]);
            if (i < n) sb.append(" ");
        }
        pw.println(sb.toString());

        pw.flush();
        pw.close();
    }
}