#include <fstream>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define inf 0x3f3f3f3f
#define mp make_pair
#define foor(it,v) for(it=v.begin();it!=v.end();++it)

typedef vector<int> VI;

vector<vector<pair<int,int> > > G;
VI dist,nr_q;
vector<pair<int,int> > ::iterator it;

bool ciclu;
vector<bool> in_q;
queue<int> q;
int n,m,i,x,y,c;

void bellman(int start)
    {
    int nod;
    dist[start]=0;
    in_q[start]=1;
    nr_q[start]=1;
    q.push(start);

    while(!q.empty() && !ciclu)
        {
        nod=q.front();
        q.pop();
        in_q[nod]=false;

        foor(it,G[nod])
            if(dist[it->first]>dist[nod]+it->second)
            {
            if(it->first==nod) continue;
            dist[it->first]=dist[nod]+it->second;
            if(!in_q[it->first])
                {
                in_q[it->first]=true;
                ++nr_q[it->first];
                if(nr_q[it->first]>n-1) ciclu=true;
                q.push(it->first);
                }
            }
        }
    }

int main()
    {
    f>>n>>m;
    G.resize(n+1);
    dist.resize(n+1,inf);
    in_q.resize(n+1,0);
    nr_q.resize(n+1,0);

    for(; m; --m)
        {
        f>>x>>y>>c;
        G[x].push_back(mp(y,c));
        }

    bellman(1);
    if(ciclu) g<<"Ciclu negativ!";
    else for(i=2; i<=n; ++i) g<<dist[i]<<' ';
    return 0;
    }