#include <bits/stdc++.h>
using namespace std;
 
const int max_buckets = 5;
int buckets;
const int INF = 1e9;
 
int n, m;
int cmax, rad;
int dist[50005];
bool viz[50005];
vector <pair <int, int> > v[50005];
 
priority_queue <pair <int, int>, vector <pair <int, int> > , greater <pair <int, int> > > pq[max_buckets + 5];
void dijkstra(){
	for(int i = 1; i <= n ; ++i) dist[i] = INF;
	
	pq[0].push({0, 1}); 
	dist[1] = 0;
	int ind = 0, cnt = 0;
	while(cnt <= buckets){
		if(ind >= buckets) ind = 0;
		if(pq[ind].empty()){
			++cnt; ++ind;
			continue ;
		}
		else cnt = 0;
		
		int nod = pq[ind].top().second;
		pq[ind].pop();
		if(viz[nod]) continue ;
		viz[nod] = 1;
		
		for(auto it : v[nod]){
			if(dist[it.first] > dist[nod] + it.second){
				dist[it.first] = dist[nod] + it.second;
				int which = (dist[it.first] / rad) % buckets;
				
				pq[which].push({dist[it.first], it.first});
			}
		}
	}
}
 
int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	int x, y, z;
	for(int i = 1; i <= m ; ++i){
		scanf("%d%d%d", &x, &y, &z);
		v[x].push_back({y, z});
	
		cmax = max(cmax, z);
	}
	
	cmax += 10;
	buckets = min(cmax, max_buckets);
	rad = cmax / buckets + 100;
	dijkstra();
	
	for(int i = 2; i <= n ; ++i){
		if(dist[i] == INF) dist[i] = 0;
		printf("%d ", dist[i]);
	}
	
	return 0;
}