#include<cstdio>
#include<set>
#include<vector>
#include<queue>
using namespace std;
priority_queue<int> p;
vector<int> v[50001],v1[50001];
int vc[50001],vec[50001],i,j,n,m,x,y,l,cost,pp,vcc[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,&cost);
    v[x].push_back(y);
    v1[x].push_back(cost);
    }
for(i=2;i<=n;i++)
    vec[i]=1000000000;
for(i=0;i<v[1].size();i++)
    {
    vec[v[1][i]]=v1[1][i];
    vc[v[1][i]]=1;
    vcc[v[1][i]]++;
    p.push(v[1][i]);
    }
while(!p.empty())
    {
    int x=p.top();
    p.pop();
    for(i=0;i<v[x].size();i++)
        if(vec[v[x][i]]>vec[x]+v1[x][i])
            {
            vec[v[x][i]]=vec[x]+v1[x][i];
            if(vc[v[x][i]]==0)
                p.push(v[x][i]);
            vc[v[x][i]]=1;
            vcc[v[x][i]]++;
            if(vcc[v[x][i]]==n+1)
                pp=1;
            }
    vc[x]=0;
    if(pp==1)
        break;
    }
if(pp==0)
    for(i=2;i<=n;i++)
        printf("%d ",vec[i]);
else
    printf("Ciclu negativ!");
return 0;
}