import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Graph {
	class Neighbour {
		int cost;
		int neighbour;

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

	ArrayList<Neighbour>[] graph;
	int[] cost;
	int n, m;

	Graph(int n) {
		graph = new ArrayList[n + 1];
		cost = new int[n + 1];
		Arrays.fill(cost, Integer.MAX_VALUE);
		cost[1] = 0;
	}

	public void addEdge(int node1, int node2, int cost) {
		if (graph[node1] == null) {
			graph[node1] = new ArrayList<Neighbour>();
		}
		graph[node1].add(new Neighbour(node2, cost));
	}

	public boolean bf() {
		boolean valid = true;
		int steps = 0;
		while (valid) {
			valid = false;
			steps++;
			for (int i = 1; i <= n; i++) {
				if (graph[i] == null || cost[i] == Integer.MAX_VALUE)
					continue;
				for (Neighbour t : graph[i]) {
					int cst = cost[i] + t.cost;
					if (cst < cost[t.neighbour]) {
						cost[t.neighbour] = cst;
						valid = true;
					}
				}
			}
			if (steps == m + 1) {
				valid = false;
			}
		}
		return (steps == m + 1) ? true : false;
	}
}

public class Main {
	private final String input;
	private final String output;
	int n, m;
	private Graph graph;

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

	private void read() throws FileNotFoundException {
		Scanner scanner = new Scanner(new FileInputStream(input));
		n = scanner.nextInt();
		m = scanner.nextInt();
		graph = new Graph(n);
		graph.n = n;
		graph.m = m;
		for (int i = 0; i < m; i++) {
			int node1 = scanner.nextInt();
			int node2 = scanner.nextInt();
			int cost = scanner.nextInt();
			graph.addEdge(node1, node2, cost);
		}
		scanner.close();
	}

	void write(boolean cycle) throws IOException {
		BufferedWriter writer = new BufferedWriter(new FileWriter(output));
		if (cycle) {
			writer.write("Ciclu negativ!");
			writer.flush();
			return;
		}
		for (int i = 2; i <= n; i++) {
			writer.write(Integer.toString(graph.cost[i]) + " ");
		}
		writer.flush();
		writer.close();
	}

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

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

}