#include <fstream>
#include <deque>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>

#define MOD 104659

using namespace std ;

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

int n, vizitat[50009], d[50009] ;

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

int lee()
{
    priority_queue<pair<int ,int> > pq ;

    pq.push({0, 1}) ;

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

        pq.pop() ;

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

        if(!vizitat[nod] || cost > d[nod])
        {

        vizitat[nod] ++ ;

        if(vizitat[nod] == n + 1)return 0 ;

        d[nod] = cost ;

        for(int f = 0 ; f < m[nod].size() ; f ++)
        pq.push({cost + m[nod][f].second, m[nod][f].first}) ;

        }
    }

    return 1 ;
}

int main()
{
    int q ;

    cin >> n >> q ;

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

        cin >> a >> b >> c ;

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

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

    if(!lee())
    {
        cout << "Ciclu negativ!" ;

        return 0 ;
    }

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

    return 0 ;
}
/*



*/