#include <fstream> 
#include <vector> 
#include <set> 
#include <algorithm>   
#define inf 0x3f3f3f3f
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct muchie
{
	long a, b, c; 
} e[800];   
long n, m, i, j, k, left, right, cost[50], f[50]; 
vector <long> v[50]; 
vector <pair<long, long> > h;   
void init() 
{     
	long i;
	cost[1]=0;
	for(i=2; i<=n; i++)
		cost[i]=inf;
	h.push_back(make_pair(0, 1));
	make_heap(h.begin(), h.end()); 
}   
void bellmanford() 
{     
	pair<long, long> per;
	long j, nod, x;     
	while(h.size())   
	{                 
		pop_heap(h.begin(), h.end());         
		per=h.back();         
		h.pop_back();
		nod = per.second;
		f[nod]=0;
		for(j=0; j<v[nod].size(); j++)
		{
			x=v[nod][j];
			if(cost[e[x].a]+e[x].c<cost[e[x].b])
			{
				cost[e[x].b]=cost[e[x].a]+e[x].c;
				if(!f[e[x].b])
				{
					f[e[x].b]=1;
					h.push_back(make_pair(cost[e[x].b], e[x].b));
					push_heap(h.begin(), h.end());
				}
			}
		}
	}
}
long ciclu_negativ()
{
	long i;
	for(i=1; i<=m; i++)
		if(cost[e[i].a]+e[i].c<cost[e[i].b])
			return 1;
	return 0;
}
int main() 
{     
	in>>n>>m;
	for(i=1; i<=m; i++)
	{
		in>>e[i].a>>e[i].b>>e[i].c;
		v[e[i].a].push_back(i);
	}
	init();
	bellmanford();
	if(ciclu_negativ())
	{
		out<<"Ciclu negativ!\n";
		return 0;     
	}     
	for(i=2; i<=n; i++)
		out<<cost[i]<<" ";
	return 0; 
}