#include<cstdio>
#include<vector>
#include<queue>
#define NMAX 50005
#define INF (1<<30)
#define US unsigned short
using namespace std;
FILE *fin,*fout;
vector <pair<US,short> > G[NMAX];
queue<int> Q;
int d[NMAX],n;
US nr[NMAX];
bool use[NMAX];
void read()
{
	fin=fopen("bellmanford.in","r");
	int m;
	US x,y;
	short c;
	fscanf(fin,"%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		fscanf(fin,"%hi %hi %hi",&x,&y,&c);
		G[x].push_back(make_pair(y,c));
	}
	fclose(fin);
}
bool bellmanford(US nod)
{
	for(US i=1;i<=n;i++)
		d[i]=INF;
	US vec;
	short cost;
	Q.push(nod);
	use[nod]=1;
	d[nod]=0;
	while(!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		use[nod]=0;
		for(size_t i=0;i<G[nod].size();i++)
		{
			vec=G[nod][i].first;
			cost=G[nod][i].second;
			if(d[vec]>d[nod]+cost)
			{
				d[vec]=d[nod]+cost;
				if(!use[vec])
				{
					if(nr[vec]>n)
						return 0;
					Q.push(vec);
					use[vec]=1;
					nr[vec]++;
				}
			}
		}
	}
	return 1;
}
void solve(US nod)
{
	fout=fopen("bellmanford.out","w");
	if(bellmanford(nod))
		for(int i=2;i<=n;i++)
			fprintf(fout,"%d ",d[i]);
	else
		fprintf(fout,"Ciclu negativ!");
	fclose(fout);
}
int main()
{
	read();
	solve(1);
	return 0;
}