#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int N_max = 50000;
const int M_max = 250000;
const int INF = 250000005;

int p, u;
vector <int> C;

int d[N_max + 1];

int lst[N_max + 1];
int vf[M_max + 1];
int urm[M_max + 1];
int cost[M_max + 1];
int nr;

bool inC[N_max + 1];
int NR[N_max + 1];

int N, M;

void adauga(int x, int y, int c)
{
    //ADAUGA IN LISTA LUI x PE y

    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    cost[nr] = c;
    lst[x] = nr;

}

int main()
{
    int i, x, y, c, poz, COST;

    in >> N >> M;

    for(i = 1; i <= M; i++)
    {
        in >> x >> y >> c;

        adauga(x, y, c);
    }

    for(i = 1; i <= N; i++) d[i] = INF;

    //INSEREZ IN COADA NODUL 1
    C.push_back(1);
    d[1] = 0;

    inC[1] = true;
    NR[1]++;

    while(p <= u)
    {
        x = C[p++];

        inC[x] = false; // IL SCOT DIN COADA

        //PARCURG VECINII y AI LUI x

        poz = lst[x];

        while(poz)
        {
            y = vf[poz];

            COST = cost[poz];

            if(d[y] > d[x] + COST)
            {
                if (!inC[y])
                {
                    u++;
                    C.push_back(y);

                    inC[y] = true;
                    NR[y]++;
                }

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

                if(NR[y] == N) //DACA AM OPTIMIZAT NODUL y DE N ORI
                {
                    //negativ = true;

                    printf("Ciclu negativ!");

                    return 0;
                }
            }

            poz = urm[poz];
        }
    }

    //if(negativ == false)
        for(i = 2; i <= N; i++) out << d[i] << " ";

    return 0;
}