#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define Nmax 50010
#define Mmax 250010
#define INF (1 << 30)

struct muchie {int a, b, c;} M[Mmax];

int n, m;
int C[Nmax], viz[Nmax];
void citire ();
vector < pair <int, int> > V[Nmax];
queue <int> Q;

int bellmanford () {
	
	int nod, fiu, i, cst, stp = 0, N = n * m;
	for (i = 2; i <= n; i++)
		C[i] = INF;
	
	Q.push (1); viz[1] = 1;
	while (!Q.empty()) {
		nod = Q.front ();
		
		for (i = 0; i < (int)V[nod].size (); i++) {
			fiu = V[nod][i].first; cst = C[nod] + V[nod][i].second;
			if (cst < C[fiu]) {
				C[fiu] = cst;
				if (!viz[fiu]) {
					Q.push (fiu);
					viz[fiu] = 1;
				} 
			}
		}
		
		viz[nod] = 0;
		Q.pop ();
		stp++; if (stp > N) break;
	}
	
	for (i = 1; i <= m; i++)
		if (C[ M[i].b ] > C[M[i].a] + M[i].c)
			return 0;
	
	return 1;
}

int main () {

	freopen ("bellmanford.in", "r", stdin);
	freopen ("bellmanford.out", "w", stdout);

	citire ();
	
	if (!bellmanford ())
		printf ("Ciclu negativ!");
	
	else 
		for (int i = 2; i <= n; i++)
			printf ("%d ", C[i]);
	
	return 0;
}

void citire () {

	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf ("%d %d %d", &M[i].a, &M[i].b, &M[i].c);
		V[M[i].a].push_back ( make_pair (M[i].b, M[i].c) );
	}
}