#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

const int OO = (1<<30)-2, DIM = 50005, DIMM = 250005;
struct much { int a, b, c; } A[DIMM];
int N, M, D[DIM], viz[DIM], curent[DIM];
vector < pair <int, int> > V[DIM];
queue <int> C;

void init ()
{
	scanf ("%d%d", &N, &M);
	for (int i = 0; i < M; i++)
	{
		scanf ("%d%d%d", &A[i].a, &A[i].b, &A[i].c);
		V[A[i].a].push_back (make_pair (A[i].b, A[i].c));
	}
	C.push (1);
	for (int i = 2; i <= N; i++)
		D[i] = OO;
}

int main ()
{
	freopen ("bellmanford.in", "r", stdin);
	freopen ("bellmanford.out", "w", stdout);
	
	init ();	
	int n, f, c, i;
	while (!C.empty ())
	{
		n = C.front ();
		curent[n] = 0;
		C.pop ();		
		
		for (i = 0; i < (int)V[n].size(); i++)
		{
			f = V[n][i].first;
			c = V[n][i].second;
			if (D[f] > D[n] + c)
			{
				D[f] = D[n] + c;
				if (curent[f] == 0)
				{
					C.push (f);
					curent[f] = 1;
					viz[f]++;
					if (viz[f] > N)
					{
						printf ("Ciclu negativ!\n");
						return 0;
					}
				}				
			}			
		}				
	}
	
	for (int i = 2; i <= N; i++)
		printf ("%d ", D[i]);
	return 0;
}