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

public class Main {

    void printPQ(PriorityQueue<Node> p){
        for(Node j : p){
            System.out.print(j.getDistance()+" ");
        }
    }

    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();
            PriorityQueue<Node> priorityQueue = new PriorityQueue<>(new DistanceComparator());
            Node[] nodeArray = new Node[n + 1];

            nodeArray[1] = new Node(1, 0);

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

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

            Node node;
            int tmp;

            while (!priorityQueue.isEmpty()) {
                node = priorityQueue.poll();
                int id = node.getId(),d;
                //for (i = 1; i <= n; i++) {
                  for (Node no : priorityQueue){
                    if(nodeArray[id].hasEdgeWith(no)) {
                        d = nodeArray[id].getDistance();
                        tmp = nodeArray[id].getDistance() + nodeArray[id].getDistanceTo(no);
                        if (tmp <  no.getDistance()) {
                            no.setDistance(tmp);
                            priorityQueue.remove(no);
                            no.setDistance(no.getDistance());
                            priorityQueue.add(no);
                        }
                    }
                }
            }

            int d;

            for (i = 2; i <= n; i++) {
                d = nodeArray[i].getDistance();
                if (d != Integer.MAX_VALUE) {
                    writer.write(String.valueOf(d) + ((i != n) ? " " : ""));
                } else {
                    writer.write(String.valueOf(0) + ((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;
        }
    }

}