#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
long long n,m,nod,cost[100003],viz[100003];
vector < pair <long long,long long> > graf[100003];
priority_queue <pair <long long,long long> , vector<pair<long long,long long> >,greater <pair<long long,long long> > > chestie;
void bfs () {
	while(chestie.size()) {
		nod=chestie.top().second;
		chestie.pop();
		if(viz[nod]==1)
			continue;
		viz[nod]=1;
		for(int i=0;i<(int)graf[nod].size();++i)
			if(cost[graf[nod][i].first]>cost[nod]+graf[nod][i].second && viz[graf[nod][i].first]==0) {
				cost[graf[nod][i].first]=cost[nod]+graf[nod][i].second;
				chestie.push(make_pair(cost[graf[nod][i].first],graf[nod][i].first));
			}
	}
}
int main () {
	long long nr1,nr2,nr3;
	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", &nr1, &nr2, &nr3);
		graf[nr1].push_back(make_pair(nr2,nr3));
	}
	for(int i=2;i<=n;++i)
		cost[i]=1e9;
	chestie.push(make_pair(0,1));bfs();
	for(int i=2;i<=n;++i)
		if(cost[i]!=1e9)
			printf("%lld ", cost[i]);
		else
			printf("0 ");
	return 0;
}