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

#define NMAX 50001
#define INF 0x3f3f3f3f

const char IN[] = "bellmanford.in", OUT[] = "bellmanford.out";

using namespace std;

int N, M;
vector<pair<int,int> > G[NMAX];
int dist[NMAX];
int timesInQ[NMAX];
bool inQ[NMAX];
int pi[NMAX];

inline void readData() {
	FILE *f =freopen(IN, "r", stdin);
	if (!f) {
		fclose(stdin);  return;
	}

	scanf(" %d %d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int s, d, c;
		scanf(" %d %d %d", &s, &d, &c);
		G[s].push_back(make_pair(d, c));
	}
	fclose(stdin);
}

int bellmanFord(int source) {
	queue<int> Q;
	memset(dist, INF, sizeof(dist));
	//memset(pi, -1, sizeof(pi));
	dist[source] = 0;
	Q.push(source);
	while (!Q.empty()) {
		int u = Q.front(); Q.pop();
		inQ[u] &= 0;
		for (auto &neigh : G[u]) {
			int v = neigh.first;
			int cost = neigh.second;
			if (dist[v] > dist[u] + cost) {
				dist[v] = dist[u] + cost;
				if (!inQ[v]) {
					if (timesInQ[v] > N) {
						cout << "Ciclu negativ!" << endl; return 1;
					}
					else {
						pi[v] = u;
						Q.push(v);
						inQ[v] |= 1;
						++timesInQ[v];
					}
				}
			}
		}
	}
	return 0;
}


int main(void){
	readData();
	freopen(OUT, "w", stdout);
	if (bellmanFord(1)) {
		fclose(stdout);
		return 0;
	}
	else {
		for (int i = 2; i <= N; ++i) {
			cout << dist[i] << " ";
		}
		cout << endl;
		fclose(stdout);
	}

	return 0;
}