//#include <cstdio>
//#include <vector>
//#include <utility>
//#include <algorithm>
//#include <queue>
//
//using namespace std;
//
//vector <int> bellman_ford (int sursa, int n, vector <vector < pair <int, int> > > &G, bool &ok) {
//	vector < pair <int, int> > :: iterator it;
//	vector <int> len, d;
//	queue <int> q;
//	len.resize (n + 1);
//	d.resize (n + 1, 1 << 30);
//	ok = true;
//	d [sursa] = 0;
//	len [sursa] = 0;
//	q.push (sursa);
//	while (ok && !q.empty ()) {
//		sursa = q.front ();
//		q.pop ();
//		for (it = G [sursa].begin (); it != G [sursa].end (); ++ it) {
//			if (d [it->first] > d [sursa] + it->second) {
//				d [it->first] = d [sursa] + it->second;
//				len [it->first] = 1 + len [sursa];
//				q.push (it->first);
//				if (len [it->first] >= n) {
//					ok = false;
//					break;
//				}
//			}
//		}
//	}
//	return d;
//}
//
//int main () {
//	vector <vector < pair <int, int> > > G;
//	vector <int> d;
//	bool ok;
//	int i, n, m, x, y, c;
//	freopen ("dijkstra.in", "rt", stdin);
//	freopen ("dijkstra.out", "wt", stdout);
//	scanf ("%d%d", &n, &m);
//	G.resize (n + 1);
//	for (i = 0; i < m; ++ i) {
//		scanf ("%d%d%d", &x, &y, &c);
//		G [x].push_back (make_pair (y, c));
//	}
//	d = bellman_ford (1, n, G, ok);
//	if (! ok) {
//		printf ("Ciclu negativ!");
//	}
//	else {
//		if (d [2] == (1 << 30)) {
//			d [2] = 0;
//		}
//		printf ("%d", d [2]);
//		for (i = 3; i <= n; ++ i) {
//			if (d [i] == (1 << 30)) {
//				d [i] = 0;
//			}
//			printf (" %d", d [i]);
//		}
//		printf ("\n");
//	}
//	return 0;
//}


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

using namespace std;

#define FILEIN "dijkstra.in"
#define FILEOUT "dijkstra.out"

const int MAXN = 50005;
const int INF = 0x3f3f3f3f;

int N, M;
vector< pair<int, int> > G[MAXN];
int Dmin[MAXN];

void ReadData() {
	ifstream fin(FILEIN);

	fin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int a, b, c;

		fin >> a >> b >> c;
		G[a].push_back(make_pair(b, c));
	}
}

void Solve() {
	bool InQueue[MAXN];
	queue<int> Q;

	memset(Dmin, INF, sizeof(Dmin));
	memset(InQueue, false, sizeof(InQueue));

	Dmin[1] = 0;
	Q.push(1);
	InQueue[1] = true;

	while (!Q.empty()) {
		int nod = Q.front();
		Q.pop();
		InQueue[nod] = false;

		for (vector< pair<int, int> >::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
			if (Dmin[nod] + it->second < Dmin[it->first]) {
				Dmin[it->first] = Dmin[nod] + it->second;
				if (!InQueue[it->first]) {
					Q.push(it->first);
					InQueue[it->first] = true;
				}
			}
	}
}

void WriteData() {
	ofstream fout(FILEOUT);

	for (int i = 2; i <= N; ++i)
		fout << (Dmin[i] < INF ? Dmin[i] : 0) << " ";
}

int main() {
	ReadData();
	Solve();
	WriteData();
}