#include <iostream>

#include <fstream>



using namespace std;



ifstream in("bellmanford.in");

ofstream out("bellmanford.out");



const int N = 50001;

const int M = 250001;

const int INF = 5000001;

int n, m, st, dr, nr, d[N], lst[N], vf[M], urm[M], cst[M], q[N+2], nrq[N];

bool inq[N];

bool exitp = false;



void adauga(int x, int y, int c)

{

    vf[++nr] = y;

    cst[nr] = c;

    urm[nr] = lst[x];

    lst[x] = nr;

}



void adauga_q(int x)

{

    if(inq[x])

    {

        return;

    }

    if(dr == N + 1)

    {

        dr = 0;

    }

    else

    {

        dr++;

    }

    q[dr] = x;

    inq[x] = true;

    nrq[x] ++;

}



int main()

{

    int x, y, c;

    in>>n>>m;

    for(int i=1; i<=m; i++)

    {

        in>>x>>y>>c;

        adauga(x, y, c);

    }



    for(int i=1; i<=n; i++)

        d[i] = INF;

    adauga_q(1);

    d[1] = 0;

    while(dr != st-1)

    {

        if(st == N + 2)

            st = 0;

        x = q[st++];

        inq[x] = false;

        for(int p = lst[x]; p != 0; p = urm[p])

        {

            y = vf[p];

            c = cst[p];

            if(d[x] + c < d[y])

            {

                d[y] = d[x] + c;

                adauga_q(y);

                if(nrq[y] == n)

                {

                    out<<"Ciclu negativ!";

                    return 0;

                }

            }

        }

    }

    for(int i=2; i<=n; i++)

        out<<d[i]<<' ';

    return 0;

}