#include <cstdio> 
#include <vector> 
#include <set> 
#include <algorithm>
#define Nmax 50005
#define inf 0x3f3f3f3f
using namespace std;
struct muchie
{
	long b, c; 
} e;
long n, m, i, j, k, left, right, cost[Nmax], f[Nmax]; 
vector <muchie> v[Nmax]; 
vector <pair<long, long> > h;   
void init() 
{     
	long i;
	cost[1]=0;
	for(i=2; i<=n; i++)
		cost[i]=inf;
	h.push_back(make_pair(0, 1));
	make_heap(h.begin(), h.end()); 
}
void bellmanford() 
{     
	pair<long, long> per;
	long nod,step=0;
	while(h.size() && step<=1LL*n*m)   
	{                 
		step++;
		pop_heap(h.begin(), h.end());         
		per=h.back();         
		h.pop_back();
		nod = per.second;
		f[nod]=0;
		for(unsigned int j=0; j<v[nod].size(); j++)
		{
			e = v[nod][j];
			if(cost[nod]+e.c<cost[e.b])
			{
				cost[e.b]=cost[nod]+e.c;
				if(!f[e.b])
				{
					f[e.b]=1;
					h.push_back(make_pair(-cost[e.b], e.b));
					push_heap(h.begin(), h.end());
				}
			}
		}
	}
}
long ciclu_negativ()
{
	long i;
	for(i=1; i<=n; i++)
		for(unsigned int j=0;j<v[i].size();j++)
			if(cost[i]+v[i][j].c<cost[v[i][j].b])
				return 1;
	return 0;
}
int main() 
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	long x,y,c;
	scanf("%d %d",&n,&m);
	for(i=1; i<=m; i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		e.b = y;
		e.c = c;
		v[x].push_back(e);
	}
	init();
	bellmanford();
	if(ciclu_negativ())
	{
		printf("Ciclu negativ!\n");
		return 0;     
	}
	for(i=2; i<=n; i++)
		printf("%d ",cost[i]);
	return 0; 
}