#include <fstream>
#include <vector>
#include <queue>
#include <climits>

#define MOD 1000000007

using namespace std;

/// timpul minim pentru toate trupele sa ajunga in nodul x
/// nodul y in care se poate ajunge cu timpul minim in general, si timpul respectiv

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

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

int n, ok = 1 ;

priority_queue<pair<int, pair<int, int> > > pq ; /// retine nodul curent

int d[50009], moduri[50009] ;

void lee(int k)
{
    for(int f = 1 ; f <= n ; f ++)
        d[f] = INT_MIN ;

    d[k] = 0 ;

    pq.push({0, {k, 1}}) ;

    while(pq.size())
    {
        pair<int, pair<int, int> > aux = pq.top() ;

        int nod = aux.second.first ;
        int cost = aux.first ;

        pq.pop() ;

        if(moduri[nod] == n)
        {
            cout << "Ciclu negativ!" ;

            ok = 0 ;

            return ;
        }

        d[nod] = cost ;

        for(int f = 0 ; f < m[nod].size() ; f ++)
        {
            int newnod = m[nod][f].first ;
            int ncost = m[nod][f].second * -1 ;

            if(cost + ncost > d[newnod])
            {
                moduri[newnod] ++ ;

                pq.push({cost + ncost, {newnod, 0}}) ;
            }
        }
    }

    return ;
}

int main()
{
    int q ;

    cin >> n >> q ;

    while(q --)
    {
        int a, b, c ;

        cin >> a >> b >> c ;

        m[a].push_back({b, c}) ;
    }

    lee(1) ;

    if(ok)
        for(int f = 2 ; f <= n ; f ++)
            cout << d[f] * -1 << " " ;

    return 0 ;
}