#include <bits/stdc++.h>
#define MAX 50100
#define INF 1e9

using namespace std;

ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

long d[MAX],cnt[MAX],s[MAX];

vector < pair < long,long> > G[MAX];
queue < long > q;

long n,m;

void dostuff()
{
    long x,y,c;
    fi>>n>>m;

    for(long i=1;i<=m;i++){
        fi>>x>>y>>c;
        G[x].push_back({y,c});
    }
}

int bf()
{
    long nxt,cst;
    long nod;

    for(long i=2;i<=n;i++)
        d[i]=INF;

    q.push(1);
    s[1]=1;

    while(!q.empty()){
        nod=q.front();
        s[nod]=0;
        q.pop();

        for(long i=0;i<G[nod].size();i++){
            nxt=G[nod][i].first;
            cst=G[nod][i].second;

            if(cst+d[nod]<d[nxt]){
                d[nxt]=cst+d[nod];

                if(s[nxt]==0){
                    q.push(nxt);
                    s[nxt]=1;
                }

                if(++cnt[nxt]>n)
                    return 0;
            }
        }
    }

    return 1;
}

int main()
{
    dostuff();

    if(bf())
        for(long i=2;i<=n;i++)
            fo<< d[i]<<" ";
    else
        fo<<"Ciclu negativ!";

    return 0;
}