#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
const int INF = 1000000000;

std::ifstream f("bellmanford.in");
std::ofstream g("bellmanford.out");

int N, M;

vector< vector<pair<int, int> > > edges;

int parent[50001];
int distances[50001];

void read(){
	int start, end , cost;
	f >> N >> M;
	for(int i = 0 ; i<= N ; ++i){
		edges.push_back(vector<pair<int,int> >());
	}
	for(int i = 0 ; i < M ; ++i){
		f >> start >> end >> cost;
		edges.at(start).push_back(make_pair(end,cost));
	}
}

void bellmanford(int S){
	for(int i = 1; i <= N ; ++i){
		distances[i] = INF;
		parent[i] = -1;
	}

	distances[S] = 0;
	//relax
	for(int i = 1; i <= N - 1; ++i){
		for(int u = 1 ; u <= N ; ++u){
			for(auto data:edges.at(u)){
				int weight = data.second;
				int v = data.first;

				if(distances[u] + weight < distances[v]){
					distances[v] = distances[u] + weight;
					parent[v] = u;
				}
			}
		}

	}
	bool stop;
	//check for negative cycles
	for(int u = 1 ; u <= N ; ++u){
		for(auto data:edges.at(u)){
			int weight = data.second;
			int v = data.first;

			if(distances[u] + weight < distances[v]){
				stop = true;
				g << "Ciclu negativ!";
				break;
			}
			
		}
	}
	if(!stop){
		for(int i = 2 ; i <= N ; ++i){
			g << distances[i] << " ";
		}
	}
}



int main(){
	read();
	bellmanford(1);
	return 0 ;	
}