#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define NM 50005
#define inf 1000000000

int N, M, cost[NM], ops;

bool isin[NM], negative_cycle;

vector < pair<int, int> > G[NM];
queue <int> Q;

int main()
{
	int a, b, c;
	
	freopen ("bellmanford.in", "r", stdin);
	freopen ("bellmanford.out", "w", stdout);
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 1; i <= M; ++i)
	{
		scanf ("%d %d %d", &a, &b, &c);
		
		G[a].push_back(make_pair(b,c));
	}	
	
	for (int i = 1; i <= N; ++i)
	{
		cost[i] = inf;
		isin[i] = 0;
	}	
	
	cost[1] = 0;
	Q.push(1);
	isin[1] = 1;
	
	while (!Q.empty() && ops < 2000000)
	{
		int nod = Q.front();
		Q.pop();
		isin[nod] = 0;
		
		++ops;
		
		for (int i = 0; i < G[nod].size(); ++i)
		{
			int nnod = G[nod][i].first;
			int adcost = G[nod][i].second;
			
			if (cost[nod] + adcost < cost[nnod])
			{
				cost[nnod] = cost[nod] + adcost;
				if (!isin[nnod])
				{
					Q.push(nnod);
					isin[nnod] = 1;
					
					++ops;
				}	
			}	
		}	
	}

	if (ops >= 2000000) printf ("Ciclu negativ!");
	else for (int i = 2; i <= N; ++i) printf ("%d ", cost[i]);	
	
	return 0;
}