import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
class Pair{
    int a;
    int b;
    int w;
    Pair(int a,  int b, int w){
        this.a = a;
        this.b = b;
        this.w = w;
    }
    public String toString(){
        return ("Weight" + w);
    }
}

public class Main {

	static List<Pair>  list;
    static int[] dist;
    static int nrn, nrm;
    static void readFromFile() throws IOException{
		FileReader file = new FileReader("bellmanford.in");
	    BufferedReader buff = new BufferedReader(file);
		int i, a, b, c;
		
	    String[] line;
	    line = buff.readLine().split(" ");
	    nrn = Integer.parseInt(line[0]);
	    nrm = Integer.parseInt(line[1]);
	    list = new ArrayList<Pair>(nrm);
	    dist = new int[nrn];
	    for(i =0; i< nrm ; i++){
	    	line = buff.readLine().split(" ");
	    	a = Integer.parseInt(line[0]);
	    	b = Integer.parseInt(line[1]);
	    	c = Integer.parseInt(line[2]);
	    	list.add(new Pair(a, b,c));
	    }
	    buff.close();
	    
    }
    static void doford() throws IOException{
    	int i, j;
    	FileWriter fw = new FileWriter("bellmanford.out");
		BufferedWriter bw = new BufferedWriter(fw);
		dist[0] = 0;
    	for( i=1; i< nrn; i++)
            dist[i] = Integer.MAX_VALUE;
        for(j = 0; j< nrm; j++){
        	if(list.get(j).a == 1)
        		dist[list.get(j).b-1] = list.get(j).w;
        }
        
        for(i =0; i < nrm -2; i++){
        	for(j =0; j< nrm ; j++){
        		if(dist[list.get(j).b-1] > dist[list.get(j).a-1] + list.get(j).w ){
        			dist[list.get(j).b-1]  = dist[list.get(j).a-1] + list.get(j).w;
        		}
        	}	
        }
        for(i =0; i< nrm; i++){
        	if(dist[list.get(i).b-1] > dist[list.get(i).a-1] + list.get(i).w ){
        		bw.write("Ciclu negativ!");
        		bw.close();
        		return;
        	}
        }
        for(i =1; i< nrn; i++){
        	bw.write(String.valueOf(dist[i]) + " ");
        }
        bw.close();
    }
    
    public static void main(String[] args) throws IOException {
		readFromFile();
		doford();
	}
}