#include <stdio.h>

#define MMAX 250005
#define NMAX 50005
#define INF 1e9

using namespace std;

FILE *fin = fopen("bellmanford.in", "r");
FILE *fout = fopen("bellmanford.out", "w");

struct muchie {int x; int y; int cost;} muchii[MMAX];

int n,m,i,j,distmin[NMAX];
bool ok;

int main()
{
    fscanf(fin, "%d%d", &n,&m);

    for(i=1; i<=m; ++i)
        fscanf(fin, "%d%d%d", &muchii[i].x,&muchii[i].y,&muchii[i].cost);

    for(i=1; i<=n; ++i)
        distmin[i] = INF;
    distmin[1] = 0;

    ok = true;
    for(i=1; i<=n-1 and ok; ++i)
    {
        ok = false;
        for(j=1; j<=m; ++j)
            if(distmin[muchii[j].x] + muchii[j].cost < distmin[muchii[j].y])
            {
                distmin[muchii[j].y] = distmin[muchii[j].x] + muchii[j].cost;
                ok = true;
            }
    }

    ok = false;
    for(j=1; j<=m; ++j)
        if(distmin[muchii[j].x] + muchii[j].cost < distmin[muchii[j].y])
        {
            distmin[muchii[j].y] = distmin[muchii[j].x] + muchii[j].cost;
            ok = true;
        }
    if(ok)
        fprintf(fout, "Ciclu negativ!");
    else
        for(i=2; i<=n; ++i)
            fprintf(fout, "%d ", distmin[i]);

    fclose(fin);
    fclose(fout);
    return 0;
}