/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package bellman_ford_infoarena;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author andrei
 */
public class Bellman_Ford_Infoarena {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new File("bellmanford.in"));
        PrintWriter pw = new PrintWriter(new File("bellmanford.out"));
        
        Integer n, m;
        n = sc.nextInt();
        m = sc.nextInt();
        System.out.print(n + "  " + m);
        System.out.flush();
        Triplet <Integer,Integer,Integer> edge;
        ArrayList <Triplet<Integer,Integer,Integer>> edges = new ArrayList<>();
        System.out.println();
        Integer v1,v2,c;
        for (int i = 1; i <= m; i++)
        {
            v1 = sc.nextInt();
            System.out.print(v1);
            v2 = sc.nextInt();
            System.out.print(v2);
            c = sc.nextInt();
            System.out.print(c);
            edge = new Triplet<>(v1,v2,c);
            edges.add(edge);
            System.out.flush();
            System.out.println();
        }
        
        int []distances = new int[n];
        Arrays.fill(distances,32000);
        distances[0]=0;
        for (int i = 0; i < n-1; i++){
            for (Triplet<Integer,Integer,Integer> obj : edges)
            {
                if ( distances[obj.getB()-1] > (distances[obj.getA()-1] + obj.getC()))
                    distances[obj.getB()-1] = distances[obj.getA()-1] + obj.getC();
            }
        }
        
//        for (int i = 0; i < n; i++)
//            System.out.print(distances[i]+ "  ");
//        
        
        boolean cycle = false;
        for (Triplet<Integer,Integer,Integer> obj : edges)
            {
                if ( distances[obj.getB()-1] > (distances[obj.getA()-1] + obj.getC()))
                    cycle = true;
            }
        
        if (cycle)
            pw.write("Ciclu negativ!");
        else 
        {
            for (int i = 1; i < n; i++)
                pw.write(distances[i]+ "  ");
        }
        pw.close();
    
    }
    
}