package com.amimun;

import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

/*
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
 */

public class Main {

    public static void main(String[] args) throws IOException {
        int m, n, i, j;
        int[][] a;

        try {
            Scanner reader = new Scanner(new FileInputStream("dijkstra.in"));
            PrintWriter writer = new PrintWriter("dijkstra.out");
            n = reader.nextInt();
            m = reader.nextInt();
            int[] dist = new int[n + 1];
            int[] prev = new int[n + 1];
            dist[1] = 0;
            PriorityQueue<Node> priorityQueue = new PriorityQueue<>(new DistanceComparator());
            Node[] nodeArray = new Node[n + 1];

            nodeArray[1] = new Node(1, dist[1]);
            priorityQueue.add(nodeArray[1]);

            for (int k = 2; k <= n; k++) {
                dist[k] = Integer.MAX_VALUE;
                nodeArray[k] = new Node(k, dist[k]);
                priorityQueue.add(nodeArray[k]);
            }

            a = new int[n + 1][n + 1];

            for (int k = 0; k < m; k++) {
                i = reader.nextInt();
                j = reader.nextInt();
                a[i][j] = reader.nextInt();
            }

            reader.close();

            Node node;
            int tmp;

            while (!priorityQueue.isEmpty()) {
                node = priorityQueue.poll();
                int id = node.getOrder();
                for (i = 1; i <= n; i++) {
                    if(a[id][i] != 0 && priorityQueue.contains(nodeArray[i])) {
                        tmp = dist[id] + a[id][i];
                        if (tmp < dist[i]) {
                            dist[i] = tmp;
                            prev[i] = id;
                            priorityQueue.remove(nodeArray[i]);
                            nodeArray[i].setDistance(dist[i]);
                            priorityQueue.add(nodeArray[i]);
                        }
                    }
                }
            }

            for (i = 2; i <= n; i++) {
                writer.write(String.valueOf(nodeArray[i].getDistance()) + ((i != n) ? " " : ""));
            }
            writer.close();

        } finally {

        }
    }

    private static class Node {
        private int order, distance;

        public Node(int _order, int _distance) {
            order = _order;
            distance = _distance;
        }

        public void setDistance(int newDist) {
            distance = newDist;
        }

        public int getDistance() {
            return distance;
        }

        public int getOrder() {
            return order;
        }

        @Override
        public boolean equals(Object o) {
            Node node = (Node) o;
            return this.getOrder() == node.getOrder();
        }
    }

    private static class DistanceComparator implements Comparator<Node> {
        @Override
        public int compare(Node a, Node b) {
            return a.getDistance() > b.getDistance() ? 1 : -1;
        }
    }

}