#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
using namespace std;

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

#define INF 0x3f3f3f3f
#define NMAX 50004

int a, b, c, N, M;
int p, q;
int k;

struct nod {
	int vf , c;
	nod(){};
	nod(int _vf,int _c){vf = _vf; c = _c;};
};

vector<nod> v[NMAX];
int d[NMAX];
int in[NMAX];

int main() {
	fin >> N >> M;
	for (int i = 0; i < M; ++i) {
		fin >> a >> b >> c;
		v[b].push_back(nod(a,c));
	}
	for (int i = 2; i <= N; ++i) d[i] = INF;
	do {
		k = 0;
		for (int i = 2; i <= N; ++i) {
			for (vector<nod> :: iterator it = v[i].begin(); it != v[i].end(); ++it) {
				if (d[it->vf] + (it->c) < d[i]) {
					d[i] = d[it->vf] + it->c;
					k = 1;
					in[i] = in[it->vf] + 1;
					/*
					if (in[i] > N) {
						fout << "Ciclu negativ!\n";
						return 0;
					}
					*/
				}
			}
		}
		for (int i = N; i >= 2; --i) {
			for (vector<nod> :: iterator it = v[i].begin(); it != v[i].end(); ++it) {
				if (d[it->vf] + (it->c) < d[i]) {
					d[i] = d[it->vf] + it->c;
					in[i] = in[it->vf] + 1;
					k = 1;
					/*
					if (in[i] > N) {
						fout << "Ciclu negativ!\n";
						return 0;
					}
					*/
				}
			}
		}
	}while(!k);
	for (int i = 2; i <= N; ++i) 
		fout << d[i] << ' ';
	fout << '\n';
	return 0;
}