#include<cstdio>
#include<vector>
#define mn 99999
using namespace std;
vector<pair<int,int> >a[50001];
int n,m,i,j,x,y,c,p,u,sum[50001],viz[50001],v[250001];
bool ok;

void citire()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&c);
		a[x].push_back(make_pair(y,c));
	}
}

void dijkstra()
{
	p=1;u=1;
	v[1]=1;
	viz[1]=1;
	sum[1]=0;
	while (p<=u){
			for(i=0;i<a[v[p]].size();i++){
				y=a[v[p]][i].first;
				c=a[v[p]][i].second;
				if(viz[y]==0){
					viz[y]=1;
					u++;
					v[u]=y;
					sum[y]=sum[v[p]]+c;
				}
				else 
					if(sum[y]>sum[v[p]]+c){
						u++;
						v[u]=y;
						sum[y]=sum[v[p]]+c;
					}
			}		
		p++;
	}
}


int main()
{
	citire();
	dijkstra();
	for(i=2;i<=n;i++)
		printf("%d ",sum[i]);
	return 0;
}