#include <cstdio>
#include <vector>
#include <queue>

#define INFINIT 999999999
#define NMAX 50010

using namespace std;

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

struct nod
{
	int ind, val, x;
};

nod nd;

int n, m;
int cmin[NMAX];
int sch;
int nr[250010];

vector<nod> v[NMAX];
queue<int>  q;

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

int main()
{
    citire();

    bmf();

    afisare();

	return 0;
}

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

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

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

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

    cmin[1] = 0;
}

void bmf()
{
    int i, x;

    q.push(1);

    while(!q.empty())
    {
        x = q.front();
        q.pop();
        for(i = 0; i < int(v[x].size()); i++)
            if (cmin[x] + v[x][i].val < cmin[v[x][i].x])
            {
                cmin[v[x][i].x]= cmin[x] + v[x][i].val;
                q.push(v[x][i].x);
                nr[v[x][i].ind]++;
                if(nr[v[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);
}