#include <bits/stdc++.h>
#define inf 1e9
#define NMAX 50005
using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");
int N , M , i , j , x , y , cost, nod,d[NMAX];
int viz[NMAX];
vector <pair <int,int> > v[NMAX];
queue <pair <int,int> > h ; // {cost, node}
int main()
{ // O(N*M) - Alg. Bellman Ford cu Queue
    f >> N >> M ;
    for (i = 1 ; i <= M ; ++i)
    {
        f >> x >> y >> cost ;
        v[x].push_back(make_pair(cost , y));
    }
    for (i = 2 ; i <= N ; i ++)
        d[i] = inf;
    d[1] = 0;
    h.push(make_pair(0,1));
    while (!h.empty())
    {
        nod = h.front().second;
        h.pop();
        for (i = 0; i < v[nod].size(); ++i)
        {
            if (d[nod] +  v[nod][i].first < d[v[nod][i].second])
            {
                d[v[nod][i].second] = d[nod] + v[nod][i].first;
                h.push(make_pair(d[v[nod][i].second] , v[nod][i].second));
            }
        }
        viz[nod] ++ ;
        if (viz[nod] == N)
        {
            g << "Ciclu negativ!" ;
            return 0;
        }
    }
    for (i = 2 ; i <= N ; i ++)
        if (d[i] == inf) g << 0 << " " ;
        else g << d[i] << " " ;
    f.close();
    g.close();
    return 0;
}