#include<stdio.h>
#include<vector>
#include<queue>
#define inf 0x3f3f3f
using namespace std;
vector <pair<int,int> > a[50001];
queue <int> q;
int i,j,m,n,viz[50001],x,y,c,k,d[50001];
int main ()
{
 freopen("bellmanford.in","r",stdin);
 freopen("bellmanford.out","w",stdout);
 scanf("%d %d" ,&n,&m);
 for(i=1;i<=m;i++)
	{
	 scanf("%d%d%d" ,&x,&y,&c);
     a[x].push_back(make_pair(y,c));
	}
 for(i=1;i<=n;i++)
	d[i]=inf;
 q.push(1);
 viz[1]=1;
 d[1]=0;
 while(!(q.empty()))
	{
	 k=q.front();

	 for(i=0;i<a[k].size();i++)
	    {
			int nod=a[k][i].first;
			int cost=a[k][i].second;
			y=d[k]+cost;
		 if(viz[nod]==0 || y<d[nod])
			{
			 q.push(nod);
			 d[nod]=y;
			 viz[nod]++;
			 if(viz[nod]>n)
				{ printf("Ciclu negativ!");
			     return 0;
		        }
			}
	    }
	 q.pop();
	}
 for(i=2;i<=n;i++)
	 printf("%d " ,d[i]);
 return 0;
}