#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

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

vector <pair <int , int > >v[50005];

int viz[50005] , dist[50005] , nod , n , x , y , c , m , cnt[50005];

int bellmanford()
{
    int nod = 1;
    queue <int> coada;
    coada.push (nod);
    viz[nod] = 1;
    dist[1] = 0;
    while (!coada.empty ())
    {
        nod = coada.front ();
        viz[nod] = 0;
        coada.pop ();

        for (int i = 0 ; i < v[nod].size () ; i++)
        {
            int vecin = v[nod][i].first;
            int cost = v[nod][i].second;

            if (dist[vecin] > cost + dist[nod])
            {
                dist[vecin] = cost + dist[nod];
                cnt[vecin] = cnt[nod] + 1;

                if (cnt[vecin] > n - 1)
                    return 0;

               if (viz[vecin] == 0)
               {
                  coada.push (vecin);
                  viz[vecin] = 1;
               }
            }
        }
    }
    return 1;
}

int main()
{
    f >> n >> m;
    for (int i = 1 ; i <= m ; i++)
    {
        f >> x >> y >> c;
        v[x].push_back (make_pair (y , c));
    }
    for (int i = 1 ; i <= n ; i++)
        dist[i] = INT_MAX;

        if (bellmanford())
        for (int i = 2 ; i <= n ; i++)
        g << dist[i] << " ";
    else
        g << "Ciclu negativ";
    return 0;
}