#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

#define inf 10000000;

vector<int>v[50001];
vector<int>c[50001];
queue<int>coada;
int n,m,d[50001],vizitat[50001];

void citire()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;++i)
	{
		int a,b,ct;
		scanf("%d %d %d",&a,&b,&ct);
		v[a].push_back(b);
		c[a].push_back(ct);
	}
}

bool b_ford(int n)
{
	for (int i=2;i<=n;i++) d[i]=inf;
	d[1]=0;
	coada.push(1);
	while (!coada.empty()) 
	{
		int x=coada.front();
		int c_actual=d[x];
		coada.pop();
		vizitat[x]=vizitat[x]+1;
		if (vizitat[x]>n) return 1;
		int nr_v=v[x].size();
		for (int i=0;i<nr_v;++i)
		{
			int vec=v[x][i];
			if (c_actual+c[x][i]<d[vec])
			{
				d[vec]=c_actual+c[x][i];
				coada.push(vec);
			}
		}
	}
	return 0;
}

int main()
{
	citire();
	if (b_ford(n)) printf("ciclu negativ!\n");
	else 
		for (int i=2;i<=n;++i)
		{
			if (d[i]>=60000000) d[i]=0;
			printf("%d ",d[i]);
		}
		return 0;
}