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

using namespace std;

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

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

priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > heap;
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", &mGraf[i].x, &mGraf[i].y, &mGraf[i].c);
        graf[mGraf[i].x].push_back (i); //din nodul mGraf[i].x pleaca muchia nr i
    }

    ans[1] = 0;
    for (int i = 2; i <= N; ans[++i] = MULT);
    heap.push (make_pair (0, 1));

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

        crt = heap.top ();
        heap.pop ();

        int nodCrt = crt.second;
        flag[nodCrt] = 0;

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

            if(ans[mGraf[indM].x] + mGraf[indM].c < ans[mGraf[indM].y]) {
                ans[mGraf[indM].y] = ans[mGraf[indM].x] + mGraf[indM].c;
                if ( !flag[mGraf[indM].y]) {
                    flag[mGraf[indM].y] = 1;
                    heap.push (make_pair (-ans[mGraf[indM].y], mGraf[indM].y));
                }
            }
        }
    }

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

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

    return 0;
}