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

public class Main {

    public static void main(String[] args) {
        int m, n, i, j, w;
        String line;
        StringTokenizer st;

        try {
            BufferedReader br = new BufferedReader(new FileReader("dijkstra.in"));
            PrintWriter writer = new PrintWriter("dijkstra.out");
            line = br.readLine();
            st = new StringTokenizer(line, " ");
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            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/2);
            }

            for (int k = 0; k < m; k++) {
                line = br.readLine();
                st = new StringTokenizer(line, " ");
                i = Integer.parseInt(st.nextToken());
                j = Integer.parseInt(st.nextToken());
                w = Integer.parseInt(st.nextToken());
                nodeArray[i].addEdge(new Edge(nodeArray[j], w));
            }
            for (int k = 1; k <= n; k++) {
                priorityQueue.add(nodeArray[k]);
            }
            br.close();

            Node node;
            int tmp;

            while (!priorityQueue.isEmpty()) {
                node = priorityQueue.poll();
                int id = node.id;
                  for (Edge ed : nodeArray[id].edgeArray){
                        tmp = nodeArray[id].distance + nodeArray[id].getDistanceTo(ed.target);
                        if (tmp <  ed.target.distance && priorityQueue.remove(ed.target)) {
                            ed.target.distance = tmp;

                            priorityQueue.add(ed.target);
                        }
                }
            }

            int d;

            for (i = 2; i <= n; i++) {
                d = nodeArray[i].distance;
                if (d < Integer.MAX_VALUE/2-1) {
                    writer.write(String.valueOf(d) + ((i != n) ? " " : ""));
                } else {
                    writer.write(String.valueOf(0) + ((i != n) ? " " : ""));
                }
            }
            writer.close();

        } catch(Exception e) {

        }
    }

    private static class Node {
        public int id, distance;
        public ArrayList<Edge> edgeArray = new ArrayList<Edge>();

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

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

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

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

            return 0;
        }

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

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

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


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

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

}