#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>

using namespace std;

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

struct edge
{
	int x, c;
};
int d[50000];
bool inq[50000];
bool nq[50000];
list<edge> ad[50000];

int main (int argc, char * const argv[]) {
	int n,m;
	
	fscanf(fin, "%d%d",&n,&m);
	
	memset(d,0x3f,sizeof(int)*n);
	d[0] = 0;
	
	for(int i=0; i<m; i++)
	{
		int x,y,c;
		fscanf(fin, "%d%d%d",&x,&y,&c);
		x--; y--;
		edge tmp;
		tmp.x = y;
		tmp.c = c;
		ad[x].push_back(tmp);
	}
	
	list<int> q;
	inq[0] = 1;
	nq[0] = 1;
	q.push_back(0);
	
	int negative = false;
	while (!q.empty() && !negative)
	{
		int x = q.front();
		q.pop_front();
		for (list<edge>::iterator i = ad[x].begin(); i!=ad[x].end(); i++)
		{
			int y = i->x;
			int c = i->c;
			if (d[y]>d[x]+c)
			{
				d[y]=d[x]+c;
				if (!inq[y])
				{
					if (nq[y]>n)
					{
						negative = true;
						break;
					}
					q.push_back(y);
					nq[y]++;
					inq[y] = true;
				}
			}
		}
	}
	
	if (negative)
		fprintf(fout, "Ciclu negativ!");
	else
		for (int i=1; i<n; i++)
			fprintf(fout, "%d ",d[i]);
	fprintf(fout, "\n");
	
	fclose(fin);
	fclose(fout);
    return 0;
}