#include <bits/stdc++.h>

using namespace std;
long long n,m,x,y,z, viz[50003],dp[50003], nod;
vector < pair <long long, long long> > graf[50003];
priority_queue < pair <long long, long long> , vector < pair <long long, long long> > , greater <pair <long long, long long> > > pq;
void dijkstra () {
	while(!pq.empty()) {
		nod=pq.top().second;
		pq.pop();
		if(viz[nod]==1)
			continue;
		viz[nod]=1;
		for(int i=0;i<(int)graf[nod].size();++i) 
			if(dp[graf[nod][i].first]>dp[nod]+graf[nod][i].second) {
				dp[graf[nod][i].first]=dp[nod]+graf[nod][i].second;
				pq.push(make_pair(dp[graf[nod][i].first], graf[nod][i].first));
			}
	}
}
int main () {
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%lld%lld", &n, &m);
	for(int i=1;i<=m;++i) {
		scanf("%lld%lld%lld", &x, &y, &z);
		graf[x].push_back(make_pair(y,z));
	}
	for(int i=2;i<=n;++i)
		dp[i]=1e9*1e9;
	pq.push(make_pair(0,1));
	dijkstra();
	for(int i=2;i<=n;++i)
		if(dp[i]!=1e9*1e9)
			printf("%lld ", dp[i]);
		else
			printf("0 ");
	return 0;
}