#include <iostream>
#include <stdio.h>
#include <climits>

#define limita 250000+10

using namespace std;

FILE *f, *g;

int n, m;
int t[3][limita], start[limita], d[limita];
int WasHere[50000+10], coada[500000+10], fr[50000+10];

void Read ()
{
    int c, x, y;
    fscanf(f, "%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        fscanf(f, "%d %d %d", &x, &y, &c);
        t[0][i] = y;
        t[1][i] = start[x];
        t[2][i] = c;
        start[x] = i;
    }
}

bool BellManFord ()
{
    for (int i = 2; i <= n; i++)
        d[i] = INT_MAX;

    coada[1] = 1;

    int pi = 1, ps = 1;
    bool okay = true;

    while (ps <= pi && okay )
    {
        int nod = coada[ps];
        WasHere[nod] = 0;
        int p = start[nod];

        while (p != 0 && okay )
        {
            if(d[nod] + t[2][p] < d[t[0][p]])
            {
                d[t[0][p]] = d[nod] + t[2][p];

                if (WasHere[t[0][p]] == 0)
                {
                    WasHere[t[0][p]] = 1; pi++;
                    coada[pi] = t[0][p];
                    fr[t[0][p]]++;
                }
            }
            if (fr[t[0][p]] > n-1)
            {
                okay = false;
            }
            p = t[1][p];
        }
        ps++;
    }
    if (okay)
        for (int i = 2; i <= n; i++)
            fprintf(g, "%d ", d[i]);
    else
        fprintf(g, "Ciclu negaiv !\n");
}


int main()
{
    f = fopen("bellmanford.in", "r");
    g = fopen("bellmanford.out", "w");

    Read();
    BellManFord();

    fclose(f);
    fclose(g);

    return 0;
}