import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;

public class Main {
	
	static private class Node{
		Vector<Muchie> muchii = new Vector<Muchie>();
		boolean isInTheQueue = false;
		int numberOfVisits = 0;
		int costFromBaseNode = Integer.MAX_VALUE;
	} 
	
	static private class Muchie{
		int cost = 0;
		int targetNode = 0;
	}
	
	
	static boolean function(int numberOfNodes, Queue<Integer> queue, Node[] graph){
		
		while(queue.isEmpty() == false) {
			
			int indiceNodCurent = queue.element();
			Node nodCurent = graph[indiceNodCurent];
			
			if(nodCurent.numberOfVisits >= numberOfNodes) {
				return false;
			}
			
			for(int i=0; i<graph[indiceNodCurent].muchii.size(); i++) {
				int indiceNodVecin = graph[indiceNodCurent].muchii.get(i).targetNode;
				int costDrum = graph[indiceNodCurent].muchii.get(i).cost;
				Node nodVecin = graph[indiceNodVecin];
				
				if(nodVecin.costFromBaseNode > nodCurent.costFromBaseNode + costDrum) {
					nodVecin.costFromBaseNode = nodCurent.costFromBaseNode + costDrum;
					if(nodVecin.isInTheQueue == false) {
						nodVecin.isInTheQueue = true;
						nodVecin.numberOfVisits ++;
						queue.add(indiceNodVecin);
					}
				}
			}
			queue.remove();
		}
		return true;
	}
	
	public static void main(String[] args){
		try {
			@SuppressWarnings("resource")
			Scanner in = new Scanner(new File("bellmanford.in"));
			PrintStream out = new PrintStream(new File("bellmanford.out"));
			
		
			int n = in.nextInt();
			int m = in.nextInt();
			
			Node[] graph = new Node[n];
			for(int i=0; i<n; i++) {
				graph[i] = new Node();			
			}
			
			for(int i=0; i<m; i++) {
				int x = in.nextInt();
				int y = in.nextInt();
				x--;
				y--;
				int c = in.nextInt();
				Muchie muchieCurenta = new Muchie();
				muchieCurenta.cost = c;
				muchieCurenta.targetNode = y;
				graph[x].muchii.add(muchieCurenta);
			}
			
			Queue<Integer> queue = new LinkedList<>();
			queue.add(0);
			graph[0].costFromBaseNode = 0;
			graph[0].isInTheQueue = true;
			if(function(n, queue, graph) == false) {
				out.printf("Ciclu negativ!");
			}else {
				for(int i=1; i<n; i++) {
					out.printf(graph[i].costFromBaseNode + " ");
				}
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
}