#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define nod first
#define cst second
#define foreach(V) for(vector <pair<int, int> > :: iterator it = (V).begin(); it != (V).end(); ++it) 

const int MAX_N = 50005;
const int INF = 0x3f3f3f3f;

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

int N, M, D[MAX_N], scos[MAX_N];
vector <pair<int, int> > G[MAX_N];

void citire()
{
	fin >> N >> M;
	
	for(int i = 1; i <= M; ++i)
	{
		int x, y, d;
		fin >> x >> y >> d;
		G[x].push_back(make_pair(y, d));
	}
}

struct cmp
{
	bool operator() (const int &a, const int &b) const
	{
		return D[a] > D[b];
	}
};

void dijkstra()
{
	priority_queue <int, vector <int>, cmp> Q;
	
	char inq[MAX_N];
	memset(D, INF, sizeof D);
	memset(inq, 0, sizeof inq);
	
	D[1] = 0;
	inq[1] = 1;
	Q.push(1);
	
	while(!Q.empty()) 
	{
		int act = Q.top();
		Q.pop();
		++scos[act];
		if(scos[act] > M) 
		{
			fout << "Ciclu negativ!";
			return;
		}
		inq[act] = 0;
		
		foreach(G[act])
			if(D[it -> nod] > D[act] + it -> cst)
			{
				D[it -> nod] = D[act] + it -> cst;
				
				if(inq[it -> nod]) continue;
				inq[it -> nod] = 1;
				Q.push(it -> nod);
			}
	}
	
	for(int i = 2; i <= N; ++i)
		fout << D[i] << " ";
}

int main()
{
	citire();
	dijkstra();
}