#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
typedef pair<int, int> pi;
struct muchie
{
    int x,y,val;
};
int main()
{
    int n,m;
    fin>>n>>m;
    int d[n+1];
    int onH[n+1];
    for(int i=2; i<=n; i++)
        {d[i]=INT_MAX;onH[i]=0;}
    d[1]=0;
    vector<pi> graf[n+1];
    int m1=m;
    vector<muchie> muchii;
    while(m1--)
    {
        muchie mu;
        fin>>mu.x>>mu.y>>mu.val;
        graf[mu.x].push_back(make_pair(mu.val,mu.y));
        muchii.push_back(mu);
    }
    priority_queue<pi, vector<pi>, greater<pi> > pq;
    pq.emplace(make_pair(0,1));
    onH[1]=1;
    long long pas = 0;
    while(!pq.empty()&&pas<1LL*n*m)
    {
        pas++;
        pi v = pq.top();
        pq.pop();
        onH[v.second]=0;
        for(auto nod:graf[v.second])
        {
            if( d[v.second] + nod.first <d[nod.second])
            {
                d[nod.second] = d[v.second] + nod.first;
                if(onH[nod.second]==0)
                    {pq.emplace(make_pair(d[nod.second],nod.second));onH[nod.second]=1;}
            }
        }
    }

    for(auto m:muchii)
    {
        if(d[m.x] != INT_MAX && d[m.x] + m.val<d[m.y])
        {
            fout<<"Ciclu negativ!";
            return 0;
        }

    }

    for(int i=2; i<=n; i++)
        fout<<d[i]<<" ";

    return 0;
}