import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        String line = null;

        BufferedReader bufferedReader;
        try {
            FileReader fileReader = new FileReader("dijkstra.in");

            bufferedReader = new BufferedReader(fileReader);
        } catch (IOException err) {
            err.printStackTrace();
            System.out.println("Unable to open input file: dijkstra.in");
            return;
        }

        Scanner scanner = new Scanner(bufferedReader);

        int nodes = scanner.nextInt();
        int noEdges = scanner.nextInt();

        Graph.Edge[] graph = new Graph.Edge[noEdges];

        for (int i = 0; i < noEdges; i++) {
            graph[i] = new Graph.Edge(scanner.next(), scanner.next(), scanner.nextInt());
        }

        Graph g = new Graph(graph);
        g.dijkstra("1");

        BufferedWriter writer = new BufferedWriter(new FileWriter("dijkstra.out"));
        for (int i = 2; i <= nodes; i++) {
            Graph.Vertex vertex = g.graph.get(Integer.toString(i));

            if (vertex == null) {
                writer.write("0 ");
                continue;
            }

            writer.write(vertex.dist.intValue() + " ");
        }
        writer.close();

        bufferedReader.close();
    }
}

class Graph {
    public final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built
    // from a set of Edges

    /**
     * One edge of the graph (only used by Graph constructor)
     */
    public static class Edge {
        public final String v1, v2;
        public final double dist;

        public Edge(String v1, String v2, double dist) {
            this.v1 = v1;
            this.v2 = v2;
            this.dist = dist;
        }
    }

    /**
     * One vertex of the graph, complete with mappings to neighbouring vertices
     */
    public static class Vertex implements Comparable<Vertex> {
        public final String name;
        public Double dist = Double.MAX_VALUE; // MAX_VALUE assumed to be infinity
        public Vertex previous = null;
        public final Map<Vertex, Double> neighbours = new HashMap<>();

        public Vertex(String name) {
            this.name = name;
        }

        private void printPath() {
            if (this == this.previous) {
                System.out.printf("%s", this.name);
            } else if (this.previous == null) {
                System.out.printf("%s(unreached)", this.name);
            } else {
                this.previous.printPath();
                System.out.printf(" -> %s(%f)", this.name, this.dist);
            }
        }

        public int compareTo(Vertex other) {
            if (dist == other.dist)
                return name.compareTo(other.name);

            return Double.compare(dist, other.dist);
        }

        @Override
        public String toString() {
            return "(" + name + ", " + dist + ")";
        }
    }

    /**
     * Builds a graph from a set of edges
     */
    public Graph(Edge[] edges) {
        graph = new HashMap<>(edges.length);

        for (Edge e : edges) {
            if (!graph.containsKey(e.v1)) {
                graph.put(e.v1, new Vertex(e.v1));
            }
            if (!graph.containsKey(e.v2)) {
                graph.put(e.v2, new Vertex(e.v2));
            }

            graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
        }
    }

    /**
     * Runs dijkstra using a specified source vertex
     */
    public void dijkstra(String startName) {
        if (!graph.containsKey(startName)) {
            System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
            return;
        }
        final Vertex source = graph.get(startName);
        source.dist = new Double(0);
        source.previous = source;
//        NavigableSet<Vertex> q = new TreeSet<>();
//
//        // set-up vertices
//        for (Vertex v : graph.values()) {
//            v.previous = v == source ? source : null;
//            v.dist = v == source ? 0 : Double.MAX_VALUE;
//            q.add(v);
//        }

        PriorityQueue<Vertex> heap = new PriorityQueue<Vertex>();

        heap.add(source);
        dijkstra(heap);
    }

    /**
     * Implementation of dijkstra's algorithm using a binary heap.
     */
    private void dijkstra(final PriorityQueue<Vertex> heap) {
        Vertex u, v;
        while (!heap.isEmpty()) {

            u = heap.remove(); // vertex with shortest distance (first iteration will return source)
            if (u.dist == Double.MAX_VALUE) {
                break; // we can ignore u (and any other remaining vertices) since they are
                // unreachable
            }

            //look at distances to each neighbour
            for (Map.Entry<Vertex, Double> a : u.neighbours.entrySet()) {
                v = a.getKey(); //the neighbour in this iteration

                final Double alternateDist = u.dist + a.getValue();
                if (alternateDist < v.dist) {
                    // shorter path to neighbour found
                    heap.remove(v);
                    v.dist = alternateDist;
                    v.previous = u;
                    heap.add(v);
                }
            }
        }
    }

    /**
     * Prints a path from the source to the specified vertex
     */
    public void printPath(String endName) {
        if (!graph.containsKey(endName)) {
            System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
            return;
        }

        graph.get(endName).printPath();
        System.out.println();
    }

    /**
     * Prints the path from the source to every vertex (output order is not guaranteed)
     */
    public void printAllPaths() {
        for (Vertex v : graph.values()) {
            v.printPath();
            System.out.println();
        }
    }
}