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

public class solution
{
	/*
	 * Algoritmul lui Ford(Bellman Ford) este un algoritm care ne determina
	 * drumul de cost minim de la un varf de start la toate celelalte varfuri ale
	 * grafului
	 * 
	 * Spre deosebire de Dijkstra care:
	 * 	1. Nu merge daca avem muchii cu cost negativ
	 * 	2. Nu ne detecteaza daca avem cicluri de cost negativ
	 * 
	 * Algoritmul lui Ford:
	 * 	1. Merge daca avem muchii de cost negativ
	 *  2. By default, algoritmul ne garanteaza drumul de cost minim de la un varf
	 *     de start la toate celelalte varfuri ale grafului, dar, daca avem in graf
	 *     un ciclu de cost negativ algortimul gaseste acest lucru
	 *     
	 * Algoritmul lui Ford este o imbunatatire a algoritmului lui Bellman-Kalaba prin
	 * faptul ca nu va mai folosi o matrice ci un vector unidimensional in care va
	 * retine costul minim al unui drum de la varful de start la un alt varf al grafului.
	 * 
	 * In plus, algoritmul lui Ford foloseste programare dinamica, spre deosebire de algoritmul
	 * lui Dijkstra care foloseste greedy.
	 * 
	 * O implementare brute-force, are complexitate de O(VE) care este mult.
	 * Aceasta implementare se poate imbunatati daca folosim un while care va opri
	 * algoritmul daca nici un nod nu a fost optimizat
	 * 
	 * O implementare foarte eficienta foloseste o coada. Aceasta implementare se bazea pe urmatorul
	 * principiu: daca un nod nu a fost optimizat la o iteratie anterioara, atunci nu are rost sa-l mai
	 * luam in seamana.
	 * Astfel, algoritmul va retine intr-o coada doar acele noduri care au fost "optimizate" la iteratia precedenta
	 * 
	 * Pentru a detecta un ciclu de cost negativ tot ce trebuie sa verificam este daca un nod a fost pus
	 * in coada de mai multe ori decat numarul de noduri. In acest caz stim cu siguranta ca acolo se afla
	 * un ciclu de cost negativ
	 * Complexitate:
	 * 		In cel mai rau caz: O(VE)
	 * 		In cel mai bun caz: O(E)
	 */
	public static void main(String[] args) throws FileNotFoundException 
	{
		Scanner scn = new Scanner(new File("bellmanford.in"));
	
		int n = scn.nextInt();
		int m = scn.nextInt();
		
		int[][] matrix = new int[n + 1][n + 1];
		
		for(int i = 0; i < m; i++)
		{
			int x = scn.nextInt();
			int y = scn.nextInt();
			int c = scn.nextInt();
			matrix[x][y] = c;
		}

		int start = 1;
		final int inf = 32000;
		
		int[] d = new int[n + 1];
		Arrays.fill(d, inf);
		d[start] = 0;
		
		boolean[] inqueue = new boolean[n + 1];
		int[] count_inqueue = new int[n + 1];
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		inqueue[1] = true;
		count_inqueue[start]++;
		
		boolean negative_cycle = false;
		
		while(!q.isEmpty() && !negative_cycle)
		{
			int p = q.poll();
			inqueue[p] = false;
			
			for(int i = 1; i <= n; i++)
			{
				if(matrix[p][i] != 0)
				{
					if(d[p] + matrix[p][i] < d[i])
					{
						if(!inqueue[i]) {
							d[i] = d[p] + matrix[p][i];
							q.add(i);
							count_inqueue[i]++;
							inqueue[i] = true;
						}
						else
						{
							if(count_inqueue[i] > n)
							{
								negative_cycle = true;
							}
						}
					}
				}
			}
		}
		
		PrintWriter pw = new PrintWriter("bellmanford.out");
		if(negative_cycle)
		{
			pw.print("Ciclu negativ!");
		}
		else
		{
			for(int i = 2; i <= n; i++)
			{
				pw.print(d[i]);
				pw.print(" ");
			}
		}
		
		pw.close();
		scn.close();
	}
}