#include <bits/stdc++.h>

#define MAX 250001
using namespace std;
ifstream f("bellmanford.in");
ofstream o("bellmanford.out");
int dist[MAX], n, m,x,c,y;
vector < pair <int, int> > G[MAX];
queue <int> Q;
int nr[MAX];
bool inQ[MAX];
bool bellman()
{
    int i, nod, x;
    bool negativ = false;
    Q.push(1);
    while(!Q.empty() && !negativ)
    {
        nod = Q.front();
        Q.pop();
        inQ[nod] = false;
        x=G[nod].size();
        for(i = 0; i < x && !negativ; i ++)
        if(dist[G[nod][i].first] > dist[nod] + G[nod][i].second)
        {
            dist[G[nod][i].first] = dist[nod] + G[nod][i].second;
            if(!inQ[G[nod][i].first])
                {
                    if(nr[G[nod][i].first] < n)
                                {
                                    Q.push(G[nod][i].first);
                                    nr[G[nod][i].first] ++;
                                    inQ[G[nod][i].first] = true;
                                } else negativ = true;
                }
        }
    }
    return negativ;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y, c));
    }
    int i;
    for(i = 1; i <= n; i ++)
        dist[i] = 99999999;
    dist[1] = 0;
    if(bellman()) 
    o << "Ciclu negativ!"<<endl;
    else for(i = 2; i <= n; i ++) 
        o << dist[i] << " ";
    return 0;
}