#include<stdio.h>
#define Nmax 50002
#define inf 1<<30
#include<vector>
#include<queue>

using namespace std;

FILE *c1,*d;
int n,m,cost[Nmax],viz[Nmax],s=1;                 // vectorul cost va memora costul drumului de la nodul s=1 la nodul de indice i din vectorul cost
typedef struct edge {int x,z;}EDGE;             // z reprezinta costul,x reprezinta b-ul din muchia a-b
vector <EDGE> a[Nmax];
queue <int> c;

void read()
{
	int i,y;
	EDGE t;
	fscanf(c1,"%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		fscanf(c1,"%d %d %d",&y,&t.x,&t.z);
		a[y].push_back(t);
	}
}

void bellman_ford()
{
	int i,primul,nod;
	viz[s]=1;                                             // aflam distanta minima de la varful s=1
	cost[s]=0;
	for(i=2;i<=n;i++)
		cost[i]=inf;
	c.push(s);
	while(c.empty()==0)
	{
		primul=c.front();
		for(i=0;i<a[primul].size();i++)
		{
			nod=a[primul][i].x;
			if(cost[primul]+a[primul][i].z<cost[nod])           
			{
				cost[nod]=cost[primul]+a[primul][i].z;
				if(viz[nod]>n&&cost[nod]<0)
				{
					fprintf(d,"Ciclu negativ!");
					return ;
				}
				viz[nod]=1;
				c.push(nod);
			}
		}
		c.pop();
	}
}

void write()
{
	int i;
	for(i=2;i<=n;i++)
		if(cost[i]==inf)
			fprintf(d,"0 ");
		else
			fprintf(d,"%d ",cost[i]);
}

int main()
{
	c1=fopen("bellmanford.in","r");
	d=fopen("bellmanford.out","w");
	read();
	bellman_ford();
	write();
	fclose(c1);
	fclose(d);
	return 0;
}