#include<cstdio>
#include<queue>
#include<vector>
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
#define maxn 50005
using namespace std;
queue <int> q;
vector < pair < int, int > > L[maxn];
int Viz[maxn],d[maxn],v[maxn],n,m,x,y,c,i;
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m>0;--m)
	{
		scanf("%d%d%d",&x,&y,&c);
		L[x].pb(mp(y,c));
	}
	q.push(1); v[1]=1;
	for(i=2;i<=n;++i)
		d[i]=INF;
	while(!q.empty())
	{
		x=q.front();
		for(i=0;i<(int)L[x].size();++i)
		{
			y=L[x][i].first;
			c=L[x][i].second;
				if(d[x]+c<d[y])
				{
					d[y]=d[x]+c;
					if(!v[y])
					{
						q.push(y);
						v[y]=1;
						if(++Viz[y]>1)
						{
							printf("Ciclu negativ!\n");
							return 0;
						}
					}
				}
		}
		q.pop();v[x]=0;
	}
	for(i=2;i<=n;++i)
		printf("%d ",d[i]);
	return 0;
}