#include <fstream>
#include <bitset>
#include <queue>
#include <vector>

using namespace std;

int dist[50001];
bitset<50001> v;
vector<pair<int,int>> g[50001];

void dijkstra(){
	queue<pair<int,int>> q;
	v[1] = 1;
	q.push(make_pair(0,1));
	while (!q.empty()){
		int x = q.front().second;
		q.pop();
		v[x] = 0;
		for (auto& i : g[x]){
			if (dist[i.second] > dist[x] + i.first){
				dist[i.second] = dist[x] + i.first;
				if (!v[i.second]){
					q.push(make_pair(dist[i.second],i.second));
					v[i.second] = 0;
				}
			}
		}
	}
}

int main(){
	ifstream f("dijkstra.in");
	ofstream c("dijkstra.out");
	int n, m,a,b,d;
	f >> n >> m;
	for (int i = 0; i < m; ++i){
		f >> a >> b >> d;
		g[a].push_back(make_pair(d, b));
	}
	for (int i = 2; i <= n; i++) dist[i] = 200000000;
	dist[1] = 0;
	dijkstra();
	for (int i = 2; i <= n;++i)
		if (dist[i] == 200000000) c << "0 ";
		else c << dist[i] << " ";
}