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

public class Main {

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

        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];
            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]);
            }

            for (int k = 0; k < m; k++) {
                i = reader.nextInt();
                j = reader.nextInt();
                w = reader.nextInt();
                nodeArray[i].addEdge(new Edge(nodeArray[j], w));
            }

            reader.close();

            Node node;
            int tmp;

            while (!priorityQueue.isEmpty()) {
                node = priorityQueue.poll();
                int id = node.getId();
                for (i = 1; i <= n; i++) {
                    if(nodeArray[id].hasEdgeWith(nodeArray[i]) && priorityQueue.contains(nodeArray[i])) {
                        tmp = dist[id] + nodeArray[id].getDistanceTo(nodeArray[i]);
                        if (tmp < dist[i]) {
                            dist[i] = tmp;
                            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 id, distance;
        private ArrayList<Edge> edgeArray = new ArrayList<Edge>();

        public Node(int _id, int _distance) {
            id = _id;
            distance = _distance;
        }

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

        public int getDistance() {
            return distance;
        }

        public int getId() {
            return id;
        }

        public void addEdge(Edge e) {
            edgeArray.add(e);
        }

        public boolean hasEdgeWith(Node n) {
            return edgeArray.contains(new Edge(n, 0));
        }

        public int getDistanceTo(Node n) {
            Iterator it = edgeArray.iterator();

            while(it.hasNext()) {
                Edge e = (Edge) it.next();
                if(e.getTarget().equals(n)) {
                    return e.getWeight();
                }
            }

            return 0;
        }

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

    public static class Edge {
        private Node target;
        private int weight;

        public Edge(Node _target, int _weight) {
            target = _target;
            weight = _weight;
        }

        public Node getTarget() {
            return  target;
        }

        public int getWeight() {
            return weight;
        }

        @Override
        public boolean equals(Object o) {
            Edge e = (Edge) o;
            return e.getTarget().equals(this.getTarget());
        }
    }

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

}