#include <bits/stdc++.h>
#define Nmax 50005

using namespace std;

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

vector < pair < int,int > > v[Nmax];
queue < int > q;
int d[Nmax],viz[Nmax],n,m,c,x,y,i,j,nod,new_nod,INF = 0x3f3f3f3f,cost; bool in_queue[Nmax];

inline void read()
{
     f >> n >> m;
     for(i = 1;i <= m;i++)
     {
         f >> x >> y >> c;
         v[x].push_back({y,c});
     }

     memset(d,INF,sizeof(d));
}

inline int bellman()
{
    q.push(1);
    d[1] = 0;
    in_queue[1] = true;
    viz[1]++;

    while(not q.empty())
    {
        nod = q.front();
        q.pop(); in_queue[nod] = false;
        int l = v[nod].size();
        for(i = 0;i < l;i++)
        {
            new_nod = v[nod][i].first;
            cost = v[nod][i].second;
            if(d[new_nod] > d[nod] + cost)
            {
                viz[new_nod]++;
                if(viz[new_nod] > n)
                    return 1;
                d[new_nod] = d[nod] + cost;
                if(not in_queue[new_nod])
                    q.push(new_nod),in_queue[new_nod] = true;
            }
        }
    }
    return 0;
}

int main()
{
    read();
    if(bellman())
        g << "Ciclu negativ!";
    else
    {
        for(i = 2;i <= n;i++)
            g << d[i] << " ";
    }
    return 0;
}