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

using namespace std;

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

vector <pair <long long,long long> > G[MAX];
long long d[MAX],s[MAX],ctr[MAX];
long long n,m;
queue <long long> q;

void dostuff()
{
    long long x,y,c;

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

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

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

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

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

        for(long 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)
                {
                    s[nxt]=1;
                    q.push(nxt);
                }

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

int main()
{
    dostuff();

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

    return 0;
}