#include <cstdio>
#define INF 100000000
#define NMAX 50000
using namespace std;

FILE * intrare = fopen("bellmanford.in","r");
FILE * iesire = fopen("bellmanford.out","w");

struct nod
{
	int ind, val;
};

nod M[NMAX][NMAX];
int n, m;
int cmin[NMAX];
int sch;
int nr[NMAX];
int nrpus[NMAX];
int coada[NMAX];

void citire();
void bmf();
void afisare();

int main()
{
    citire();

    bmf();

    afisare();

	return 0;
}

void citire()
{
    int i, x, y, cst;
	nod nd;

	fscanf(intrare,"%d%d",&n,&m);

	for(i = 1; i <= m; i++)
	{
		fscanf(intrare,"%d%d%d",&x,&y,&cst);
		nd.ind = y;
		nd.val = cst;
		M[x][++nr[x]] = nd;
	}

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

    cmin[1] = 0;
}

void bmf()
{
    int inc, sf;
    int i, x;
    inc = sf = 1;
    coada[1] = 1;
    sch = 0;
    while(inc <= sf)
    {
        x = coada[inc++];
        for(i = 0; i <= nr[x]; i++)
            if (cmin[x] + M[x][i].val < cmin[M[x][i].ind])
            {
                cmin[M[x][i].ind]= cmin[x] + M[x][i].val;
                coada[++sf]=M[x][i].ind;
                nrpus[M[x][i].ind]++;
                if(nrpus[M[x][i].ind] >= n)
                {
                    sch = 1;
                    return;
                }
            }
    }
}

void afisare()
{
    int i;
	if(sch)
		fprintf(iesire,"Ciclu negativ!");
	else
		for(i = 2; i <= n; i++)
			fprintf(iesire,"%d ", cmin[i]);
    fprintf(iesire,"\n");
	fclose(iesire);
}