import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.*;

/**
 * Created by Ada on 7/26/2016.
 */
public class Main {

    public static void main(String[] argv) {
        Graph graph;
        Integer n,m;

        //read
        try {
            Scanner scanner = new Scanner(new FileInputStream("dijkstra.in"));
            n = scanner.nextInt();
            m = scanner.nextInt();
            graph = new Graph();
            for (int i = 1; i <= n; i++) {
                graph.addNode(i);
            }

            for (int j = 1; j <= m; j++) {
                Integer x = scanner.nextInt();
                Integer y = scanner.nextInt();
                Integer cost = scanner.nextInt();
                graph.addEdge(x, y, cost);
            }
            scanner.close();
        } catch (Exception exception) {
            exception.printStackTrace();
            return;
        }

        //initialize arrays
        Long[] distances = new Long[n + 1];
        Boolean[] inQueue = new Boolean[n + 1];

        Arrays.fill(distances, (long)Integer.MAX_VALUE);
        Arrays.fill(inQueue, false);
        distances[1] = 0L;

        //compute
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(1);
        while (!queue.isEmpty()) {
            Integer current = queue.getFirst();
            queue.removeFirst();
            inQueue[current] = false;

            for (Edge edge : graph.getNode(current).getNeighbours()) {
                Integer neighbour = edge.getNodeId();
                Integer cost = edge.getCost();
                if (distances[neighbour] > distances[current] + cost) {
                    distances[neighbour] = distances[current] + cost;
                    if (!inQueue[neighbour]) {
                        queue.add(neighbour);
                        inQueue[neighbour] = true;
                    }
                }
            }
        }

        //print result
        try {
            PrintWriter printWriter = new PrintWriter("dijkstra.out");
            for (int i = 2; i <= n; i++) {
                printWriter.write((distances[i] < Integer.MAX_VALUE ? distances[i] : 0) + " ");
            }
            printWriter.write("\n");
            printWriter.close();
        } catch (Exception exception) {
            exception.printStackTrace();
        }
    }

    private static class Graph {
        private Map<Integer, Node> nodes;

        public Graph() {
            this.nodes = new HashMap<Integer, Node>();
        }

        public void addNode(Integer nodeId) {
            this.nodes.put(nodeId, new Node(nodeId));
        }

        public void addEdge(Integer sourceId, Integer destinationId, Integer cost) {
            if ((this.nodes.get(sourceId) == null) || (this.nodes.get(destinationId) == null)) {
                return;
            }
            this.nodes.get(sourceId).addNeighbour(new Edge(destinationId, cost));
        }

        public Node getNode(Integer nodeId) {
            return this.nodes.get(nodeId);
        }
    }

    private static class Node {
        private Integer id;
        private List<Edge> neighbours;

        public Node(Integer id) {
            this.id = id;
            this.neighbours = new LinkedList<Edge>();
        }

        public void addNeighbour(Edge edge) {
            this.neighbours.add(edge);
        }

        public List<Edge> getNeighbours() {
            return neighbours;
        }

        public Integer getId() {
            return id;
        }
    }

    private static class Edge {
        private Integer nodeId;
        private Integer cost;

        public Edge(Integer node, Integer cost) {
            this.nodeId = node;
            this.cost = cost;
        }

        public Integer getNodeId() {
            return nodeId;
        }

        public Integer getCost() {
            return cost;
        }
    }
}