#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

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

const int nmax = 5e4, inf = 2e9;

vector<pair<int, int>> edge[nmax + 1];
vector<int> minn(nmax + 1, inf);

int n, m, x, y, c;

bool muchicmp(pii a, pii b) {
	return a.second < b.second;
}

void djikstra() {
	queue<pii> pq;
	pq.push({0, 1});
	minn[1] = 0;
	while(!pq.empty()) {
		int cc = pq.front().first, cn = pq.front().second;
		pq.pop();
		if(minn[cn] < cc)
			continue;
		for(pii &nxt : edge[cn]) {
			int nc = cc + nxt.second, nn = nxt.first;
			if(minn[nn] > nc) {
				minn[nn] = nc;
				pq.push({nc, nn});
			}
		}
	}
}

int main() {
	fin >> n >> m;
	for(int i = 1; i <= m; i++) {
		fin >> x >> y >> c;
		edge[x].push_back({y, c});
	}
	for(int i = 1; i <= n; i++)
		sort(edge[i].begin(), edge[i].end(), muchicmp);
	djikstra();
	for(int i = 2; i <= n; i++)
		fout << ((minn[i] == inf) ? 0 : minn[i]) << " ";
	return 0;
}