#include<cstdio>
#include<vector>
#include<deque>
using namespace std;
int n,m,i,x,y,c,p,u,viz[50001],dist[50001];
vector<pair<int,int> >a[50001];
deque<int>d;

void afisare();

void citire()
{
    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,&c);
        a[x].push_back(make_pair(y,c));
    }
}

void bell(int x)
{
    u=1;p=1;
    d.push_back(x);
    while(!d.empty()){
        x=d.front();
        d.pop_front();
        for(i=0;i<a[x].size();i++){
            y=a[x][i].first;
            c=a[x][i].second;

            if((viz[y]==0 || dist[y]>dist[x]+c)&& y!=1)viz[y]++,dist[y]=dist[x]+c,d.push_back(y);
            if(viz[y]>=n){printf("Ciclu negativ!");return ;}
        }
    }
    afisare();
}

void afisare()
{
    for(i=2;i<=n;i++)printf("%d ",dist[i]);
}

int main()
{
    citire();
    bell(1);
    return 0;
}