import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;

public class Main {
	 static ArrayList<Pair<Pair<Integer, Integer>, Integer>>  adj;
	 static int[] dist;

	 
	public static void main(String[] args) throws IOException {
		 BufferedReader bf = new BufferedReader(new FileReader("bellmanford.in"));
		 //PrintStream out = new PrintStream();
		 OutputStream out = new BufferedOutputStream ( new FileOutputStream("bellmanford.out") );
	     String tmp[] = bf.readLine().split(" ");
	     int n = Integer.parseInt(tmp[0]);
	     int m = Integer.parseInt(tmp[1]);
	   
	
		 dist = new int[n+1];
		 adj = new ArrayList<Pair<Pair<Integer, Integer>, Integer>>();
		 for(int i=1; i<=n; i++) {
			 
			 dist[i] = Integer.MAX_VALUE;
		 }
		 dist[1] = 0;
		int x,y,d;
	     for (int i = 0; i < m; i++) {
           tmp = bf.readLine().split(" ");
            x = Integer.parseInt(tmp[0]);
            y = Integer.parseInt(tmp[1]);
            d = Integer.parseInt(tmp[2]);
           adj.add(new Pair(new Pair<Integer, Integer>(x, y), d) );
           if (x == 1)        	   
        	   dist[y] = d;
	     }
	     for (int i = 1; i < m - 2; i++){
	    	 for (Pair<Pair<Integer, Integer>, Integer> p : adj)
	    		 if ( dist[p.x.x] != Integer.MAX_VALUE && dist[p.x.y] > dist[p.x.x] + p.y){
	    			 dist[p.x.y] =  dist[p.x.x] + p.y;
	    		 }		 
	     }
	     boolean ok = true;
	     for (Pair<Pair<Integer, Integer>, Integer> p : adj)
	    	 if ( dist[p.x.x] != Integer.MAX_VALUE && dist[p.x.y] > dist[p.x.x] + p.y){
	    		 out.write(("Ciclu negativ!").getBytes());
	    		 ok = false;
	    		 break;
	    	 }
	    if (ok){		 
		    for (int i = 2 ;i <= n;i++){
		    	if (dist[i] == Integer.MAX_VALUE)
		    		out.write(("0 ").getBytes());
		    	else
		    		out.write((dist[i]+" ").getBytes());
		    }
	    }
	    out.write(("\n").getBytes());
		 out.flush();
		 out.close();
		 bf.close();
		 
	}
}

	class Pair <A,B>{
		A x;
		B y;
		public Pair(A x, B y) {
			super();
			this.x = x;
			this.y = y;
		}
	}