#include <fstream> 
#include <vector> 
#include <set> 
#include <algorithm>   
#define inf 0x3f3f3f3f
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
struct muchie
{
	int b, c; 
} e;
long n, m, i, j, k, left, right, cost[50], f[50]; 
vector <muchie> 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;
	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++)
		{
			//e = v[nod][j];
			if(cost[nod]+v[nod][j].c<cost[v[nod][j].b])
			{
				cost[v[nod][j].b]=cost[nod]+v[nod][j].c;
				if(!f[v[nod][j].b])
				{
					f[v[nod][j].b]=1;
					h.push_back(make_pair(cost[v[nod][j].b], v[nod][j].b));
					push_heap(h.begin(), h.end());
				}
			}
		}
	}
}
long ciclu_negativ()
{
	long i;
	for(i=1; i<=n; i++)
		for(int j=0;j<v[i].size();j++)
		if(cost[i]+v[i][j].c<cost[v[i][j].b])
			return 1;
	return 0;
}
int main() 
{
	int x,y,c;
	in>>n>>m;
	for(i=1; i<=m; i++)
	{
		in>>x>>y>>c;
		e.b = y;
		e.c = c;
		v[x].push_back(e);
	}
	init();
	bellmanford();
	if(ciclu_negativ())
	{
		out<<"Ciclu negativ!\n";
		return 0;     
	}
	for(i=2; i<=n; i++)
		out<<cost[i]<<" ";
	return 0; 
}