#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 done[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;
	int dealt = 0;
	do {
		for (int i = 2; i <= N; ++i) {
            for (vector<nod> :: iterator it = v[i].begin(); it != v[i].end(); ++it) {
                if (d[it->vf] != INF && d[it->vf] + (it->c) < d[i]) {
                    d[i] = d[it->vf] + it->c;
					if (d[i] != INF && !done[i]) {
						done[i] = true;
						++dealt;
					}
                    k = 1;
                    in[i] = in[it->vf] + 1;
                    /*
                    if (in[i] > N) {
                        fout << "Ciclu negativ!\n";
                        return 0;
                    }
                    */
                }
            }
        }
	}while(!k || dealt != N-1);
	for (int i = 2; i <= N; ++i) 
		fout << d[i] << ' ';
	fout << '\n';
	return 0;
}