#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 50001
#define M 250001
#define INF 1e9

typedef struct element element;

struct element
{
    int vf, c, urm;
};

int lst[N], d[N], nrq[N], q[N], n, nr, st, dr;
element succesori[M];
bool inq[N];

int urmator(int p)
{
    if (p == N - 1)
    {
        return 0;
    }
    return p + 1;
}

void adauga_q(int x)
{
    dr = urmator(dr);
    q[dr] = x;
    inq[x] = true;
    nrq[x]++;///la fiecare intrare in q, am gasit un drum mai lung optim
}

bool q_vida()
{
    return (st == urmator(dr));
}

void sterge_q()
{
    inq[q[st]] = false;
    st = urmator(st);
}

bool bellman(int x0)
{
    int i;
    for (i = 1; i <= n; i++)
    {
        if (i == x0)
        {
            d[i] = 0;
            adauga_q(i);
        }
        else
        {
            d[i] = INF;
        }
    }
    while (!q_vida())
    {
        int x = q[st];
        sterge_q();
        int p = lst[x];
        while (p != 0)
        {
            int y = succesori[p].vf;
            int c = succesori[p].c;
            if (d[x] + c < d[y])
            {
                d[y] = d[x] + c;
                if (!inq[y])///daca y nu e deja in q
                {
                    adauga_q(y);///il adaug
                    if (nrq[y] == n)///am gasit un drum optim de lungime n
                    {
                        return false;///deci am circuit negativ
                    }
                }
            }
            p = succesori[p].urm;
        }
    }
    return true;
}

void adauga(int x, int y, int c)
{
    ++nr;
    succesori[nr].vf = y;
    succesori[nr].c = c;
    succesori[nr].urm = lst[x];
    lst[x] = nr;
}

int main()
{
    FILE *in, *out;
    in = fopen("bellmanford.in", "r");
    out = fopen("bellmanford.out", "w");
    int m, i;
    fscanf(in, "%d%d", &n, &m);
    for (i = 0; i < m; i++)
    {
        int x, y, c;
        fscanf(in, "%d%d%d", &x, &y, &c);
        adauga(x, y, c);
    }
    fclose(in);
    if (!bellman(1))
    {
        fprintf(out, "Ciclu negativ!");
    }
    else
    {
        for (i = 2; i <= n; i++)
        {
            fprintf(out, "%d ", d[i]);
        }
    }
    fclose(out);
    return 0;
}