#include <stdio.h>
#include <vector>
#include <queue>
#define DIM 50010
using namespace std;
int n, m, x, y, z, i, j, v[DIM], d[DIM], ok, k, p, u, nr[DIM];
const int INF=(1<<30);

struct st{
	int v, c;
};

vector<st> L[DIM];
st aux;
queue<int> c;

int main(){
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i=2; i<=n; i++)
		d[i]=INF;
	for(i=1; i<=m; i++)
	{
		scanf("%d %d %d", &x, &y, &z);
		aux.v=y;
		aux.c=z;
		L[x].push_back(aux);
	}
	c.push(1);
	v[1]=1;
	nr[1]=1;
	while(!c.empty())
	{
		x=c.front();
		c.pop();
		v[x]=0;
		for(i=0; i<L[x].size(); i++)
		{
			y=L[x][i].v;
			
			if(d[y]>d[x]+L[x][i].c)
			{
				d[y]=d[x]+L[x][i].c;
				if(v[y]==0)
				{
					if(nr[y]==n)
					{
						printf("Ciclu negativ!\n");
						return 0;
					}
					nr[y]++;
					c.push(y);
					v[y]=1;
				}
			}
		}
	}
	for(i=2; i<=n; i++)
		printf("%d ", d[i]);
	printf("\n");
	return 0;
}