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

#define costMaxim 1000000000
#define numarNoduriMaxim 50005

using namespace std;

vector< pair<int, int> > listaAdiacenta[numarNoduriMaxim];

int main()
{
    ifstream in("bellmanford.in");

    int numarNoduri;
    int numarMuchii;

    in>> numarNoduri>> numarMuchii;

    for( int i = 0, nod1, nod2, cost; i<numarMuchii; ++i )
    {
        in>> nod1>> nod2>> cost;

        listaAdiacenta[nod1].push_back(make_pair(nod2, cost));
    }
    in.close();

    queue<int> tail;
    bitset<numarNoduriMaxim> existaInTail(false);

    vector<int> distanta(numarNoduriMaxim, costMaxim);
    vector<int> numarParcurgeriNod(numarNoduriMaxim, 0);

    bool existaCicluNegativ = false;

    distanta[1] = 0;
    tail.push(1);
    existaInTail[1].flip();

    while( !tail.empty() && !existaCicluNegativ )
    {
        int nod = tail.front();
        tail.pop();

        existaInTail[nod] = false;

        for( auto &it : listaAdiacenta[nod] )
        {
            if( distanta[nod] < costMaxim )
            {
                if( distanta[it.first] > distanta[nod] + it.second )
                {
                    distanta[it.first] = distanta[nod] + it.second;

                    if( !existaInTail[it.first] )
                    {
                        if( numarParcurgeriNod[it.first] > numarNoduri )
                        {
                            existaCicluNegativ = true;
                            break;
                        }
                        else
                        {
                            tail.push(it.first);
                            existaInTail[it.first] = true;
                            ++numarParcurgeriNod[it.first];
                        }
                    }
                }
            }
        }
    }

    ofstream out("bellmanford.out");
    if( !existaCicluNegativ )
    {
        for( int i = 2; i<= numarNoduri; ++i )
        {
            out<< distanta[i]<<" ";
        }
    }
    else
    {
        out<< "Ciclu negativ!";
    }
    out.close();

    return 0;
}