#include <cstdio>
#include <list>
#include <queue>
#define NMax 50000 

using namespace std;

int n,m,lg[NMax],vall,x,y;
queue<int> q;
list<int> li[NMax],val[NMax];

void dfs(long now) {
	q.push(now);
	while(!q.empty()) {
		now=q.front();
		for(list<int>::iterator it=li[now].begin(),vl=val[now].begin();it!=li[now].end();it++,vl++) {
			if(lg[now] + *vl <lg[*it] || lg[*it]==0){
				lg[*it]=lg[now] + *vl;q.push(*it);
			}
		}
		q.pop();
	}
}

int main() {
	freopen("dijkstra.in","rt",stdin);
	freopen("dijkstra.out","wt",stdout);

	scanf("%ld %ld",&n,&m);

	for(long i=1;i<=n;i++) {
		scanf("%ld %ld %ld",&x,&y,&vall);
		li[x].push_back(y);
		val[x].push_back(vall);
	}

	dfs(1);

	for(long i=2;i<=n;i++)
		printf("%ld ",lg[i]);
	printf("\n");

	return 0;
}