import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.logging.Level;
import java.util.logging.Logger;

class Edge {
	
	public int source;
	public int destination;
	public int cost;
	
	public Edge(int s, int d, int c) {
		source = s;
		destination = d;
		cost = c;
	}
	
}

class MyScanner3 {
    BufferedReader br;
    StringTokenizer st;
 
    public MyScanner3() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    public MyScanner3(String name) throws FileNotFoundException {
    	InputStream input = new FileInputStream(name);
        br = new BufferedReader(new InputStreamReader(input));
    }
 
    public String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
 
    public long nextLong() {
        return Long.parseLong(next());
    }
 
    public double nextDouble() {
        return Double.parseDouble(next());
    }
 
    public String nextLine(){
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

class Graph3 {
	
	public int nrEdges;
	public Edge[] edges;
	
	public Graph3(int n) {
		nrEdges = n;
		edges = new Edge[nrEdges];
	}
	
	public void addEdge(Edge edge, int pos) {
		edges[pos] = edge;
	}
	
	public void readData(MyScanner3 sc) {
		
		int src, dest, cost;
		
		for(int i = 0; i < nrEdges; i++) {
			src = sc.nextInt();
			dest = sc.nextInt();
			cost = sc.nextInt();
			this.addEdge(new Edge(src, dest, cost), i);
		}
		
	}
	
}

class Main {
	
	public static int M;
	public static int N;
	public static int[] d;
	public static int[] chainCost;
	
	public static boolean bellmanFord(Graph3 g, int root) {
		
		int u, v, c;
		
		d[root] = 0;
		
		for(int i = 1; i <= N - 1; i++) {
			for(int j = 0; j < M; j++) {
				u = g.edges[j].source;
				v = g.edges[j].destination;
				c = g.edges[j].cost;
				if((d[u] != Integer.MAX_VALUE) && (d[v] > d[u] + c)) {
					d[v] = d[u] + c;
				}
			}
		}
		
		for(int i = 0; i < M; i++) {
			u = g.edges[i].source;
			v = g.edges[i].destination;
			c = g.edges[i].cost;
			if((d[u] != Integer.MAX_VALUE) && (d[v] > d[u] + c)) {
				return true;
			}
		}
		
		return false;
		
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		
		String outs = "";
		MyScanner3 sc = new MyScanner3("bellmanford.in");
		N = sc.nextInt();
		M = sc.nextInt();
		d = new int[N + 1];
		for(int i = 2; i <= N; i++) {
			d[i] = Integer.MAX_VALUE;
		}
		//chainCost = new int[N + 1];
		Graph3 g = new Graph3(M);
		g.readData(sc);
		boolean answer = bellmanFord(g, 1);
		if(answer) {
			outs += "Ciclu negativ!\n";
		}
		else {
			for(int i = 2; i <= N; i++) {
				outs = outs + d[i] + " ";
			}
		}
		try {
			PrintWriter out = new PrintWriter(new File("bellmanford.out"));
			out.print(outs);
			out.close();
		} catch (IOException ex) {
            Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
			//Logger.getLogger(Dijkstra.class.getName()).log(Level.SEVERE, null, ex);
        }
	
	}
}