/* Bellman-Ford O(V*E)
    - single source shortest path algorithm
    - +detects negative cycles
    - works for directed/undirected(modified by including two edges in each direction to make it directed) graphs with both negative and positive weights
*/

#include <bits/stdc++.h>
#define maxN 50002
#define oo INT_MAX
FILE *fin = freopen("bellmanford.in", "r", stdin);
FILE *fout = freopen("bellmanford.out", "w", stdout);
using namespace std;

struct Node{
	int node, weight;
};

int nodes, edges;
// store the weighted edges
vector <Node> g[maxN];
// use queue for a more efficient way of relaxing edges
queue <int> q;
// distance from source to all nodes
int ans[maxN];
// source can always be chaged (just set it as node 0 by default)
int source = 1;
// keep track of already-in-queue nodes
bitset <maxN> inQ;
// check the length of the path up to a certain nodes
int cnt[maxN];

void bellman_ford() {
	q.push(source); inQ.set(source);

	while (!q.empty()) {
		int u = q.front();
		q.pop(); inQ.reset(u);

		for (Node it : g[u]) {
			int v = it.node;
			int weight = it.weight;

			// check if it is worth relaxing the edge
			if (ans[v] > ans[u] + weight) {
				ans[v] = ans[u] + weight;
 				if(!inQ.test(v)) {
					if(cnt[v] >= nodes) { // check for negative cycle
						printf("Ciclu negativ!");
						exit(0);
					}
					q.push(v);
					inQ.set(v);
					cnt[v] ++;
				}
			}
		}
	}
}

int main() {
	scanf ("%d%d", &nodes, &edges);
	for (int i = 0; i < edges; ++ i) {
		int from, to, weight;
		scanf("%d%d%d", &from, &to, &weight);
		g[from].push_back(Node{to, weight});	// index from 0
	}

	//initialize distance to all nodes but the source with infinity
	for (int i = 2; i <= nodes; ++i)
		ans[i] = oo;

	bellman_ford();

	for (int i = 1; i <= nodes; ++i)
		if(i!= source)
			printf("%d ", (ans[i] < oo ? ans[i] : 0));

	return 0;
}