#include <stdio.h>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

#define INF 1<<30

using namespace std;

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

int N, M;
vector< vector< pair<int,int> > > neigh;
vector< pair<int,int> > minHeap;
vector<int> d;
vector<int> in_heap;


void read(){

	in >> N >> M;

	d.resize(N+1);
	d.assign(N+1, INF);

	in_heap.resize(N+1);

	for(int i = 0; i <= N; ++i){
		vector< pair<int,int> > v;
		neigh.push_back(v);
	}

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

	minHeap.push_back(make_pair(0,1));
	make_heap(minHeap.begin(),minHeap.end());
}


int BellmanFord(){

	pair<int,int> p;
	long long count = 0;

	while(minHeap.size() && count <= 1LL*N*M){

		count++;
		
		pop_heap(minHeap.begin(),minHeap.end());
		p = minHeap.back();
		minHeap.pop_back();
		int u = p.second;
		in_heap[u] = 0;

		for(int i = 0; i < neigh[u].size(); ++i){
			int v = neigh[u][i].second;
			int c = neigh[u][i].first;
			int dist = d[u] + c;
			if(d[v] > dist){
				d[v] = dist;
				if(in_heap[v] == 0){
					in_heap[v] = 1;
					minHeap.push_back(make_pair(-d[v],v));
					push_heap(minHeap.begin(), minHeap.end());
				}
			}
		}
	}

	for(int i = 1; i <= N; ++i){
		for(unsigned int j = 0; j < neigh[i].size(); ++j){
			int u = i;
			int c = neigh[i][j].first;
			int v = neigh[i][j].second;
			int dist = d[u] + c;
			if(d[v] > dist)
				return -1;
		}
	}

	return 0;

}



int main(){

	read();
	int rez = BellmanFord();

	if(rez == -1)
		out << "Ciclu negativ!";
	else{
		for(unsigned int i = 2; i < d.size(); ++i){
			out << d[i] << " ";
		}
	}
}