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

#define NMAX 50001
#define INF 123456789

using namespace std;

ofstream g("bellmanford.out");

vector<pair <int, int> > adList[NMAX];
int distances[NMAX];
queue<int> Q;
int inQueue[NMAX], visited[NMAX];
int N, M;

void bellman(){

	Q.push(1);
	inQueue[1] = 1;
	visited[1]++;

	while(!Q.empty()){
		int node = Q.front();
		Q.pop();
		inQueue[node] = 0;

		vector<pair<int, int> > :: iterator it = adList[node].begin();

		while(it != adList[node].end()){
			if(distances[it->first] > distances[node] + it->second){
				distances[it->first] = distances[node] + it->second;

				visited[it->first]++;

				if(visited[it->first] >= N){
					g << "Ciclu negativ!";
					return;
				}

				if(inQueue[it->first] == 0){
					Q.push(it->first);
					inQueue[it->first] = 1;
				}
			}
			it++;
		}
	}

	for(int i = 2; i <= N; i++)
		g << distances[i] << " ";
}
int main(){
	ifstream f("bellmanford.in");
	int a, b, c;

	f >> N >> M;
	for(int i = 0; i < M; i++){
		f >> a >> b >> c;
		adList[a].push_back(make_pair(b, c));
	}

	f.close();

	for(int i = 2; i <= N; i++)
		distances[i] = INF;
	bellman();

	g.close();
	return 0;
}