import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new FileReader("dijkstra.in"));
        DirectedGraph graph = new DirectedGraph(scanner.nextInt());
        int connections = scanner.nextInt();
        for (int i=0; i<connections; i++) {
            graph.addConnection(scanner.nextInt()-1, scanner.nextInt()-1, scanner.nextInt());
        }
        scanner.close();

        PrintWriter printWriter = new PrintWriter("dijkstra.out");
        int[] shortestPaths = graph.getShortestPathsFrom(0);
        for (int i=1; i<shortestPaths.length; i++ ) {
            printWriter.printf("%d ", shortestPaths[i]);
        }
        printWriter.close();

    }
}

class DirectedGraph {
    class NodeEntry {
        List<DestinationEntry> adjNodes;
        int distanceFromSource = Integer.MAX_VALUE;

        void add(int destination, int distance) {
            if (adjNodes == null) {
                adjNodes = new LinkedList<>();
            }
            adjNodes.add(new DestinationEntry(destination, distance));
        }
    }

    class DestinationEntry {
        int destination;
        int distance;

        DestinationEntry(int destination, int distance) {
            this.destination = destination;
            this.distance = distance;
        }
    }

    class QueueEntry implements Comparable<QueueEntry> {
        int destination;
        int distance;

        QueueEntry(int destination, int distance) {
            this.destination = destination;
            this.distance = distance;
        }

        @Override
        public int compareTo(QueueEntry entry) {
            return Integer.compare(this.distance, entry.distance);
        }
    }

    private NodeEntry[] adjList;

    DirectedGraph(int nodes) {
        adjList = new NodeEntry[nodes];
        for (int i=0; i<nodes; i++) {
            adjList[i] = new NodeEntry();
        }
    }

    public void addConnection(int source, int destination, int distance) {
        // todo: validate input
        if (source == destination) {
            return;
        }
        adjList[source].add(destination, distance);
    }

    int[] getShortestPathsFrom(int source) {
        // todo: validate input
        Queue<QueueEntry> queue = new PriorityQueue<>();
        queue.offer(new QueueEntry(source, 0));

        while (!queue.isEmpty()) {
            QueueEntry min = queue.poll();
            NodeEntry destinationNode = adjList[min.destination];

            if (min.distance < destinationNode.distanceFromSource) {
                destinationNode.distanceFromSource = min.distance;
                if (destinationNode.adjNodes != null) {
                    for (DestinationEntry adjNode : destinationNode.adjNodes) {
                        queue.offer(new QueueEntry(adjNode.destination, min.distance + adjNode.distance));
                    }
                }
            }
        }

        int[] minDistances = new int[adjList.length];
        for (int i=0; i<adjList.length; i++) {
            minDistances[i] = (adjList[i].distanceFromSource < Integer.MAX_VALUE) ? adjList[i].distanceFromSource : 0;
            adjList[i].distanceFromSource = Integer.MAX_VALUE;
        }

        return minDistances;
    }


}