#include <bits/stdc++.h>
using namespace std;
int n,m;
struct egh{
	int from,to,len,next;
}a[200010];
int pre[20010];
int k;
queue<int>q;
bool f[20010];
int d[20010];
void add(int u,int v,int l){
	a[++k]={u,v,l,pre[u]};
	pre[u]=k;
}
int main(){
	cin>>n>>m;
	int x,y,len;
	for (int i=1;i<=m;i++){
		cin>>x>>y>>len;
		add(x,y,len);
	}
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	q.push(1);
	f[1]=true;
	while (!q.empty()){
		int u=q.front();
		for (int i=pre[u];i!=0;i=a[i].next){
			int v=a[i].to;
			if (d[u]+a[i].len<d[v]){
				d[v]=d[u]+a[i].len;
				if (!f[v]){
					q.push(v);
					f[v]=true;
				}
			}
		}
		q.pop();
		f[u]=false;
	}
	for (int i=2;i<=n;i++)cout<<d[i]<<endl;
	return 0;
}