#include<cstdio>
#include<vector>
using namespace std;
vector<pair<int,int> > v[50001];
int vec[50001],vc[50001],c[500001];
int main ()
{freopen ("bellmanford.in","r",stdin);
freopen ("bellmanford.out","w",stdout);
int n,m,i,j,k,x,q,qq;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    {scanf("%d%d%d",&k,&x,&q);
    v[k].push_back(make_pair(x,q));
    }
for(i=1;i<=n;i++)
    vec[i]=1000000000;
vec[1]=0;
vc[1]=1;
j=qq=1;
c[1]=1;
for(i=1;i<n;i++)
    {q=qq;
    for(;j<=q;j++)
        {for(k=0;k<v[c[j]].size();k++)
            if(vec[c[j]]+v[c[j]][k].second<vec[v[c[j]][k].first])
                {vec[v[c[j]][k].first]=vec[c[j]]+v[c[j]][k].second;
                if(vc[v[c[j]][k].first]==0)
                    {vc[v[c[j]][k].first]=1;
                    qq++;
                    c[qq]=v[c[j]][k].first;
                    }
                }
        vc[c[j]]=0;
        }
    }
for(j=1;j<=n;j++)
    for(k=0;k<v[j].size();k++)
        if(vec[j]+v[j][k].second<vec[v[j][k].first])
            {printf("Ciclu negativ!");
            return 0;
            }
for(i=2;i<=n;i++)
    printf("%d ",vec[i]);
return 0;
}