#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define mx INT_MAX
#define pq priority_queue

using namespace std;

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

struct cmp{
	bool operator()(const pair<int, int> &a, const pair<int, int> &b){
		return(a.nd > b.nd);
	}
};

int n, m, x, y, c, dp[50100];
vector <pair <int, int> > v[50100]; 
set <pair <int, int>, cmp> heap;

int main(){
	ios_base :: sync_with_stdio(0);
	in.tie(0);
	in >> n >> m;

	for(int i = 1; i <= m; i++){
		in >> x >> y >> c;
		v[x].pb(mp(y, c));
	}

	for(int i = 1; i <= n; i++) dp[i] = mx;
	dp[1] = 0;
	pair <int, int> x;
	heap.insert(mp(1, 0));

	while(!heap.empty()){
		
		x = mp(heap.begin()->st, heap.begin()->nd);
		heap.erase(heap.begin());
		
		for(auto it : v[x.st]){
			
			int nod = it.st;
			int dist = it.nd;
			
			if(dp[x.st] + dist < dp[nod]){
				
				if(dp[nod] == mx) heap.erase(mp(nod, dp[nod]));
				
				dp[nod] = dp[x.st] + dist;
				
				heap.insert(mp(nod, dp[nod]));
				
			}
		
		}
	
	}

	for(int i = 2; i <= n; i++){
		if(dp[i] == mx) out << "0 ";
		else out << dp[i] << ' ';
	}

	return 0;
}