#include<fstream> 
#include<vector> 
#include<queue>
#include<cstring>
#define INF 0x3f3f3f3f 
#define NMAX 50100
using namespace std; 

ifstream in("bellmanford.in"); 
ofstream out("bellmanford.out"); 

int N, M, dist[NMAX], cnt_Q[NMAX];
bool in_Q[NMAX], ciclu_negativ;

vector< pair < int, int > > G[NMAX]; 

struct comp
{
	bool operator() (const int &A, const int &B) 
	{
		return dist[A] > dist[B]; 
	}
}; 

priority_queue< int, vector<int>, comp > Q; 

void solve() 
{
	memset(dist, INF, sizeof(dist));
	
	Q.push(1);
	dist[1] = 0;
	in_Q[1] = true; 
	
	while(!Q.empty() && !ciclu_negativ) 
	{
		int nod = Q.top(); 
		Q.pop(); 
		in_Q[nod] = false; 
		
		for(vector< pair < int, int > > :: iterator it = G[nod].begin(); it != G[nod].end(); ++it) 
			{
				if(dist[it -> first] > dist[nod] + it -> second) 
				{
					dist[it -> first] = dist[nod] + it -> second; 
			      
					if(!in_Q[it -> first]) 
					{
					  if(cnt_Q[it -> first] > N) ciclu_negativ = true;
                      else 
                      {
					    Q.push(it -> first); 
						in_Q[it -> first] = true; 
					    ++cnt_Q[it -> first];
					  }
					}
				}
		}
	}
}

int main() 
{
	int i, x, y, c;
	in >> N >> M; 
	
	for(i = 1; i <= M; i++) 
	{
		in >> x >> y >> c; 
		G[x].push_back(make_pair(y,c));
	}

	solve();
	if(ciclu_negativ) 
		out << "Ciclu negativ!"; 
	else 
	for(i = 2; i <= N; i++) 
		out << (dist[i] < INF ? dist[i] : 0) << " "; 
}