import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	private class Neighbour {
		final int next;
		final int cost;

		public Neighbour(int next, int cost) {
			this.next = next;
			this.cost = cost;
		}
	}

	int n, m, negativeTest[];
	ArrayList<Neighbour>[] graph;
	int distance[];
	final String input;
	final String output;

	Main(String input, String output) {
		this.input = input;
		this.output = output;
	}

	void read() throws IOException {
		Scanner scanner = new Scanner(new FileReader(input));
		n = scanner.nextInt();
		m = scanner.nextInt();
		graph = new ArrayList[n + 1];
		distance = new int[n + 1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		for (int i = 0; i < m; i++) {
			int node1 = scanner.nextInt();
			int node2 = scanner.nextInt();
			int cost = scanner.nextInt();
			if (graph[node1] == null) {
				graph[node1] = new ArrayList<Neighbour>();
			}
			graph[node1].add(new Neighbour(node2, cost));
		}
		scanner.close();
	}

	boolean bf() {
		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		distance[1] = 0;
		int[] visited = new int[n + 1];
		boolean[] inQueue = new boolean[n + 1];
		while (!(queue.size() == 0)) {
			int el = queue.getFirst();
			inQueue[el] = false;
			queue.removeFirst();
			if (graph[el] == null || distance[el] == Integer.MAX_VALUE) {
				continue;
			}
			for (Neighbour neighbour : graph[el]) {
				if (distance[el] + neighbour.cost < distance[neighbour.next]) {
					distance[neighbour.next] = distance[el] + neighbour.cost;
					if (!inQueue[neighbour.next]) {
						inQueue[neighbour.next] = true;
						queue.addLast(neighbour.next);
					}
					if (++visited[neighbour.next] >= n) {
						return false;
					}
				}
			}
		}
		return true;
	}

	void write(boolean result) throws IOException {
		BufferedWriter writer = new BufferedWriter(new FileWriter(output));
		if (result == false) {
			writer.write("Ciclu negativ!");
		} else {
			for (int i = 2; i <= n; i++) {
				writer.write(Integer.toString(distance[i]) + " ");
			}
		}
		writer.flush();
	}

	void solve() throws IOException {
		read();
		write(bf());
	}

	public static void main(String[] args) throws IOException {
		Main main = new Main("bellmanford.in", "bellmanford.out");
		main.solve();
	}

}