#include <stdio.h>
#include <vector>
#define dmax 2000000000

using namespace std;
FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");

vector<int>a[50005];

int v[50005],n,m,x,y,z,use[50005],i,r,apar[50005];
int belmann(int k){

int i,c[500105],p,u,ct=0,nc;
vector<int>::iterator it;

p=1;
u=1;
c[p]=1;
for(i=2;i<=n;i++)
v[i]=dmax;
use[1]=1;

while(p<=u)
{
for(it=a[c[p]].begin();it!=a[c[p]].end();++it)
{
ct++;
if (ct%2==1)nc=*it;
else {
r=*it;
if (v[c[p]]+r<v[nc]){
    v[nc]=v[c[p]]+*it;
    if (use[nc]==0){u++;c[u]=nc;use[nc]=1;if (apar[nc]>n)return 0;apar[nc]++;}
}
}
}

use[c[p]]=0;
p++;
}


return 1;
}


int main()
{
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{
fscanf(f,"%d%d%d",&x,&y,&z);
a[x].push_back(y);
a[x].push_back(z);
}

if (belmann(1)==0)fprintf(g,"%s","Ciclu negativ!");
else
 for(i=2;i<=n;i++)
 fprintf(g,"%d ",v[i]);
fclose(g);
return 0;
}