import java.util.*;
import java.io.*;

public class Main {
    static public class Edge {
    Node firstNode;
    Node secondNode;
    int weight;
    
    public Edge() {
        firstNode = new Node();
        secondNode = new Node();
    }
};
    static public class Node {
    int index;
    int weight;
    Node ancestor;
};
    
    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new File("C:\\Users\\Iustin1\\Documents\\NetBeansProjects\\Bellman-Ford\\src\\bellmanford.in"));
        PrintWriter printer = new PrintWriter(new File("C:\\Users\\Iustin1\\Documents\\NetBeansProjects\\Bellman-Ford\\src\\bellmanford.out"));
        ArrayList<Edge> graph = new ArrayList<>();
        int numberOfNodes = scanner.nextInt();
        int numberOfEdges = scanner.nextInt();
        
        ArrayList<Node> nodes = new ArrayList<>();
        for(int i = 0; i < numberOfNodes; i++) {
            Node node = new Node();
            node.index = i+1;
            node.weight = Integer.MAX_VALUE;
            nodes.add(node);
        }
        nodes.get(0).weight = 0;
        
        for(int i = 0; i < numberOfEdges; i++) {
            Edge edge = new Edge();
            edge.firstNode = nodes.get(scanner.nextInt()-1);
            edge.secondNode = nodes.get(scanner.nextInt()-1);
            edge.weight = scanner.nextInt();
            graph.add(edge);
        }
        
        for(int i = 0; i < numberOfNodes - 1; i++) 
            for(Edge edge : graph)  {
                if(edge.secondNode.weight > edge.firstNode.weight + edge.weight) {
                    edge.secondNode.weight = edge.firstNode.weight + edge.weight;
                    edge.secondNode.ancestor = edge.firstNode;
                }
            }
        boolean hasNegativeCycle = false;
        for(Edge edge : graph) 
                if(edge.secondNode.weight > edge.firstNode.weight + edge.weight) {
                    hasNegativeCycle = true;
                    break;
                }
        if(hasNegativeCycle)
            printer.println("Ciclu negativ!");
        else
            for(int i = 1; i < numberOfNodes; i++)
                printer.println(nodes.get(i).weight);
    }
    
}