#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;

#define maxN 50005
#define INF INT_MAX
#define PB push_back
#define MKP make_pair

vector <pair <int , int> > V[maxN];
queue <int> Q;

int cost[maxN] , cont[maxN];
int N , M;

int main ()
{
	freopen ("bellmanford.in" , "r" , stdin);
	freopen ("bellmanford.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	int a , b , c;
	
	while (M --)
	{
		scanf ("%d %d %d" , &a , &b , &c);
		
		V[a].PB(MKP (b , c));
	}
	
	for (int i = 0 ; i <= N + 1 ; ++i)
		cost[i] = INF;
	
	cost[1] = 0;
	Q.push(1);
	
	while (!Q.empty())
	{
		int root = Q.front();
		Q.pop();
		
		for (unsigned int i = 0 ; i < V[root].size() ; ++i)
		{
			int node = V[root][i].first;
			int now_cost = V[root][i].second;
			
			if (cost[node] < cost[root] + now_cost)
				continue;
			
			++cont[node];
			
			if (cont[node] > N)
			{
				printf("Ciclu negativ!");
				return 0;
			}
			
			cost[node] = cost[root] + now_cost;
			Q.push(node); 
		}
	}
	
	for (int i = 2 ; i <= N ; ++i)
		printf("%d " , cost[i]);
	
	return 0;
}