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 {
        FileReader fileReader = new FileReader("dijkstra.in");
        BufferedReader bufferedReader = new BufferedReader(fileReader);

        Scanner scanner = new Scanner(bufferedReader);

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

        Map<String, Graph.Vertex> graph = new HashMap<String, Graph.Vertex>(noEdges);

        for (int i = 0; i < noEdges; i++) {
            String v1 = scanner.next();
            String v2 = scanner.next();
            Double dist = scanner.nextDouble();

            if (!graph.containsKey(v1)) {
                graph.put(v1, new Graph.Vertex(v1));
            }
            if (!graph.containsKey(v2)) {
                graph.put(v2, new Graph.Vertex(v2));
            }

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

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

        StringBuilder output = new StringBuilder();

        for (int i = 2; i <= nodes; i++) {
            Graph.Vertex vertex = g.graph.get(Integer.toString(i));

            if (vertex == null || vertex.dist == Double.MAX_VALUE) {
                output.append("0");
            } else {
                output.append(vertex.dist.intValue());
            }
            output.append(" ");
        }
        BufferedWriter writer = new BufferedWriter(new FileWriter("dijkstra.out"));
        writer.write(output.toString());
        writer.close();

    }
}

class Graph {
    public final Map<String, Vertex> graph;

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

    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.equals(other.dist)) {
                return name.compareTo(other.name);
            }

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

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

    public Graph(Map<String, Vertex> graph) {
        this.graph = graph;
    }

    /**
     * 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 = 0.0;
        source.previous = source;

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

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

    /**
     * Implementation of dijkstra's algorithm using a min 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);
                }
            }
        }
    }
}