import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new FileReader( "bellmanford.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("bellmanford.out");
        int[] shortestPaths = graph.getShortestPathsFrom(0);
        if (shortestPaths != null) {
            for (int i = 1; i < shortestPaths.length; i++) {
                printWriter.printf("%d ", shortestPaths[i]);
            }
        } else {
            printWriter.print("Ciclu negativ!");
        }
        printWriter.close();
    }
}

class DirectedGraph {

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

        int destination;
        int distance;
    }

    class Node {
        List<Connection> connections;
        int distanceFromSource = Integer.MAX_VALUE;

        void addConnection(int destination, int distance) {
            if (connections == null) {
                connections = new LinkedList<>();
            }
            connections.add(new Connection(destination, distance));
        }
    }

    private Node[] nodes;

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

    void addConnection(int source, int destination, int distance) {
        if (source < 0 || source >= nodes.length) {
            throw new IllegalArgumentException("invalid source: " + source);
        }
        if (destination < 0 || destination >= nodes.length) {
            throw new IllegalArgumentException("invalid destination: " + destination);
        }
        if (source == destination) {
            return;
        }
        nodes[source].addConnection(destination, distance);
    }

    int[] getShortestPathsFrom(int source) {
        if (source < 0 || source >= nodes.length) {
            throw new IllegalArgumentException("invalid source: " + source);
        }
        nodes[source].distanceFromSource = 0;
        int i = 0;
        for (; i<nodes.length-1 && expandNodes(); i++);
        if (i == nodes.length-1 && expandNodes()) {
            return null;
        }
        return gatherAndResetShortestPaths();
    }

    private int[] gatherAndResetShortestPaths() {
        int[] shortestPaths = new int[nodes.length];
        for (int i=0; i<nodes.length; i++) {
            shortestPaths[i] = (nodes[i].distanceFromSource < Integer.MAX_VALUE) ? nodes[i].distanceFromSource : 0;
            nodes[i].distanceFromSource = Integer.MAX_VALUE;
        }
        return shortestPaths;
    }

    private boolean expandNodes() {
        boolean graphUpdated = false;
        for (Node node : nodes) {
            if (node.distanceFromSource < Integer.MAX_VALUE && node.connections != null) {
                for (Connection connection : node.connections) {
                    if (nodes[connection.destination].distanceFromSource > node.distanceFromSource + connection.distance) {
                        nodes[connection.destination].distanceFromSource = node.distanceFromSource + connection.distance;
                        graphUpdated = true;
                    }
                }
            }
        }
        return graphUpdated;
    }
}