#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int DMAX = 50003;
vector <pair <int, int> > G[DMAX];
queue <int> q;
int C[DMAX];
bool viz[DMAX];

int main () {

    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out", "w", stdout);
    int N, M, a, b, c, i;
    scanf ("%d%d", &N, &M);
    while (M--) {
        scanf ("%d%d%d", &a, &b, &c),
        G[a].push_back (make_pair (b, c));
    }
    q.push (1);
    viz[1] = 1;
    while (!q.empty ()) {
        a = q.front ();
        q.pop ();
        for (i = 0; i < G[a].size (); ++i)
            if (viz[G[a][i].first]){
                if (C[a] + G[a][i].second - C[G[a][i].first] < 0) {
                    printf ("Ciclu negativ!");
                    return 0;
                }
                if (C[a] + G[a][i].second < C[G[a][i].first])
                    q.push (G[a][i].first),
                    C[G[a][i].first] = C[a] + G[a][i].second;
            }
            else
                q.push (G[a][i].first),
                C[G[a][i].first] = C[a] + G[a][i].second,
                viz[G[a][i].first] = 1;
    }
    for (i = 2; i <= N; ++i)
        printf ("%d ", C[i]);

}