#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream cin ("bellmanford.in") ;
ofstream cout ("bellmanford.out") ;

int n ;

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

int viz[50009], valoare[50009] ;

int main()
{
    int q ;

    cin >> n >> q ;

    for(int f = 1 ; f <= n ; f ++)
        valoare[f] = INT_MAX ;

    while(q --)
    {

        int a, b, cost ;

        cin >> a >> b >> cost ;

        v[a].push_back({b, cost}) ;

    }

    deque<pair<int, int> > dq ;

    dq.push_back({1, 0}) ;

    viz[1] ++ ;

    while(dq.size())
    {

        int nod_curent = dq.front().first ;
        int cost_curent = dq.front().second ;

        dq.pop_front() ;

        for(int f = 0 ; f < v[nod_curent].size() ; f ++)
        {

            int next_nod = v[nod_curent][f].first ;
            int cost = v[nod_curent][f].second ;

            if(cost_curent + cost < valoare[next_nod])
            {

                valoare[next_nod] = cost_curent + cost ;

                dq.push_back({next_nod, valoare[next_nod]}) ;

                viz[nod_curent] ++ ;

                if(viz[nod_curent] > n){
                    cout << "Ciclu negativ!" ;

                    return 0 ;

                }

            }

        }

    }

    int mn = INT_MAX ;

    for(int f = 2 ; f <= n ; f ++)
        cout << valoare[f] << " " ;

    return 0;
}