#include <fstream>
#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];

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

int main () {
    fin >> N >> M;
    for (int i = 1; i <= M; i++) {
        fin >> 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]) {
            fout << "Ciclu negativ!" << '\n';
            return 0;
        }
    }

    for (int i = 2; i <= N; i++) {
        fout << ans[i] << " ";
    }
    fout << '\n';

    return 0;
}