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

using namespace std;

int n, m, u, v, w;

vector< pair<int, int> > edges[100005];
vector < int > dist;
vector < int > visited;
vector < bool > isInside;
queue<int> q;

bool bellman_ford(){
	int u;
	while (!q.empty()){
		u = q.front(); q.pop();
		isInside[u] = false;
		if (visited[u] > n - 1){ cout << "Ciclu negativ!\n"; return false; }
		for (int i = 0; i < edges[u].size(); i++){
			int v = edges[u][i].first, w = edges[u][i].second;
			if (dist[v] > dist[u] + w){
				dist[v] = dist[u] + w;
				if (!isInside[v]){
					q.push(v); visited[v] ++; isInside[v] = true;
				}
			}
		}
	}
	return true;
}

int main(){
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	scanf("%d%d", &n, &m);
	//cin >> n >> m;
	dist.push_back(0), isInside.push_back(true), visited.push_back(0);
	for (int i = 1; i < n; i++)
		dist.push_back(1 << 30), isInside.push_back(false), visited.push_back(0);
	q.push(0);
	for (int i = 0; i < m; i++){
		//cin >> u >> v >> w;
		scanf("%d%d%d", &u, &v, &w);
		u--, v--;
		edges[u].push_back(make_pair(v, w));
	}
	if (bellman_ford()){
		for (int i = 1; i < n; i++)
			cout << dist[i] << " ";
	}
	cout << "\n";
	
	return 0;
}