#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
#define infile "bellmanford.in"
#define outfile "bellmanford.out"
#define n_max 50005
#define INF 1<<31
#define pb push_back
#define mkp make_pair
#define FOR(g,it) \
	for(vector <pair <int, int> > ::iterator it = g.begin(); it!=g.end(); ++it)
using namespace std;

vector< pair <int, int> > v[n_max];//graful

vector < int > dist(n_max,INF);

int n;

void citeste()
{
	freopen(infile,"r",stdin);
	
	int m, x, y, c;
	
	scanf("%d %d",&n, &m);
	
	while(m--)
	{
		scanf("%d %d %d",&x, &y, &c);
		
		v[x].pb( mkp(y,c) );
	}
	
	fclose(stdin);
}



int bellmanford()
{
	vector < int > cnt_queue(n_max, 0);//cnt_queue[i] = de cate ori l-am pus pe i in coada
	
	bitset <n_max> in_queue;//in_queue[i] == 1 daca i este pus in coada
	
	queue <int> q;//coada
	
	q.push(1);
	in_queue[1] = 1;
	dist[1] = 0;
	
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		in_queue[x] = 0;
		
		FOR(v[x],it)
			if(dist[x] + it->second < dist[it->first])
			{
				dist[it->first] = dist[x] + it->second;
				
				if(!in_queue[it->first])
				{
					if(cnt_queue[it->first] > n)
						return 0;
					
					q.push(it->first);
					in_queue[it->first] = 1;
					cnt_queue[it->first]++;
				}
			}
	}
	
	return 1;
}



void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	if( bellmanford() )
		for(int i=2;i<=n;i++)
			printf("%d ",dist[i]);
		
	else
		printf("Ciclu negativ!");
	
	fclose(stdout);
}


int main()
{
	citeste();
	afiseaza();
	
	return 0;
}