#include<fstream.h>
#include<queue>
#define inf 1000000000
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int i,j,n,m,x,y,d[50001],viz[50001],k,z,nr[50001],nod,cost;
queue<int> q;
vector< pair<int,int> > a[50001]; 
int main ()
{
 f>>n>>m;
 for(i=1;i<=n;i++){
	 d[i]=inf;
 }
 for(i=1;i<=m;i++)
    {f>>x>>y>>z;
     a[x].push_back(make_pair(y,z));
	} 
 d[1]=0;
 q.push(1);
 nr[1]=1;
 viz[1]=1;
 while(!q.empty()){
	k=(int)q.front();
	for(i=0;i<=((int)a[k].size()-1);i++)
	{
		nod=a[k][i].first;
		cost=a[k][i].second;
		if( d[nod]>d[k]+cost){
			d[nod]=d[k]+cost;
			nr[nod]++;
			if(nr[nod]>=n){
				g<<"Ciclu negativ!";
				return 0;
			}
			if(viz[nod]==0)
			{viz[nod]=1;
			 q.push(nod);
			} 
		}
	}
	viz[k]=0;
    q.pop();
    }
 for(i=2;i<=n;i++)
	g<<d[i]<<' ';
 return 0;
}