#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

#define NMAX 50010
#define MMAX 250010
#define MULT 60000000

struct muchie {int x, y, c;} m[MMAX];

queue<int> Q;
vector<int> graf[NMAX];
int N, M;
int ans[NMAX], flag[NMAX];

int main () {
    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out", "w", stdout);

    scanf ("%d%d", &N, &M);
    for (int i = 1; i <= M; i++) {
        scanf ("%d%d%d", &m[i].x, &m[i].y, &m[i].c);
        graf[m[i].x].push_back (i); //din nodul m[i].x pleaca muchia nr i
    }

    ans[1] = 0;
    for (int i = 1; i <= N; ans[++i] = MULT);
    Q.push (1);

    pair<int, int> crt;
    long long pasCrt = 0;
    while ( !Q.empty () && pasCrt <= (long long) N * M) {
        pasCrt++;

        int nod = Q.front();
        Q.pop();
        flag[nod] = 0;

        int ind;
        for (int i = 0; i < graf[nod].size (); i++) {
            ind = graf[nod][i];

            if(ans[m[ind].x] + m[ind].c < ans[m[ind].y]) {
                ans[m[ind].y] = ans[m[ind].x] + m[ind].c;
                if ( !flag[m[ind].y]) {
                    flag[m[ind].y] = 1;
                    Q.push (m[ind].y);
                }
            }
        }
    }

    for (int i = 1; i <= M; i++) {
        if (ans[m[i].x] + m[i].c < ans[m[i].y]) {
            printf ("Ciclu negativ!\n");
            return 0;
        }
    }

    for (int i = 2; i <= N; i++) {
        printf ("%d ", ans[i]);
    }
    printf ("\n");

    return 0;
}