#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;

vector<pair <int,int> >mu[50001];
queue<int>q;
int z[50001];
bool ok;

int cost[50001];
int main()
{int n,i,j,m,p,d,vecin,pret;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
    scanf("%d%d%d",&p,&j,&d);
    mu[p].push_back(make_pair(j,d));
}
for(i=2;i<=n;i++)cost[i]=19876;

q.push(1);
while(!q.empty()&&!ok)
{
    p=q.front();
    q.pop();
    d=mu[p].size();
    z[p]++;
    if(z[p]==n)ok=true;
    for(j=0;j<d;j++)
    {vecin=mu[p][j].first;
    pret=mu[p][j].second;


        if(cost[vecin]>cost[p]+pret)
        {
            cost[vecin]=cost[p]+pret;
            q.push(vecin);
        }
    }

}
 if(ok)printf("Ciclu negativ!");
    else for(i=2;i<=n;i++)printf("%d ",cost[i]);


    return 0;
}