import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class BellmanFord {
	private final List<List<Integer>> adj;
	private final List<List<Integer>> costs;

	BellmanFord(List<List<Integer>> adj, List<List<Integer>> costs) {
		this.adj = adj;
		this.costs = costs;
	}

	List<Integer> getMinimumDistances(int startNode) {
		int N = adj.size();
		List<Integer> dists = new ArrayList<Integer>();
		List<Integer> counts = new ArrayList<Integer>();
		Queue<Integer> queue = new LinkedList<Integer>();

		for (int i = 0; i < N; ++i) {
			counts.add(0);
			dists.add(Integer.MAX_VALUE);
		}

		counts.set(startNode, 1);
		dists.set(startNode, 0);
		queue.add(startNode);

		while (!queue.isEmpty()) {
			int node = queue.poll();

			List<Integer> siblings = adj.get(node);
			List<Integer> weights = costs.get(node);

			for (int i = 0; i < siblings.size(); ++i) {
				int sibling = siblings.get(i);
				int weight = weights.get(i);
				int newWeight = dists.get(node) + weight;

				if (dists.get(sibling) > newWeight) {
					dists.set(sibling, newWeight);
					queue.add(sibling);
					counts.set(sibling, 1 + counts.get(sibling));

					if (counts.get(sibling) >= N) {
						return new ArrayList<Integer>();
					}
				}
			}
		}

		return dists;
	}
}

public class Main {
	public static void main(String args[]) throws IOException {
		InputStream inputStream = new FileInputStream("bellmanford.in");
		Scanner scanner = new Scanner(inputStream);

		OutputStream outputStream = new FileOutputStream("bellmanford.out");
		PrintWriter writer = new PrintWriter(outputStream);

		int N = scanner.nextInt();
		int M = scanner.nextInt();

		List<List<Integer>> adj = new ArrayList<List<Integer>>();
		List<List<Integer>> costs = new ArrayList<List<Integer>>();

		for (int i = 0; i < N; ++i) {
			adj.add(new ArrayList<Integer>());
			costs.add(new ArrayList<Integer>());
		}

		while (M-- > 0) {
			int x = scanner.nextInt() - 1;
			int y = scanner.nextInt() - 1;
			int c = scanner.nextInt();

			adj.get(x).add(y);
			costs.get(x).add(c);
		}

		BellmanFord graph = new BellmanFord(adj, costs);
		List<Integer> distances = graph.getMinimumDistances(0);

		if (distances.isEmpty()) {
			writer.print("Ciclu negativ!");
		} else {
			for (int i = 1; i < distances.size(); ++i) {
				int distance = distances.get(i);
				writer.print(distance + " ");
			}
		}

		writer.println();
		writer.flush();

		outputStream.close();
		writer.close();

		inputStream.close();
		scanner.close();
	}
}