#include<fstream>
#include<string.h>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define pb push_back
vector<int> vec[50000];
vector<int> cost[50000];
int care[200001];
int aint[200001];
int n,m;

inline int maxim(int a,int b){
	if(a>b)
		return a;
	else
		return b;
}
int x,poz;
void inserare(int nod,int l,int r){
	if(l==r){
		aint[nod]=x;
		care[nod]=poz;
		return;
	}
	int mid=(l+r)/2;
	if(mid<poz)
		inserare((2*nod)+1,mid+1,r);
	else
		inserare(2*nod,l,mid);
	if(aint[2*nod]>aint[(2*nod)+1]){
		aint[nod]=aint[2*nod+1];
		care[nod]=care[2*nod+1];
	}
	else{
		aint[nod]=aint[(2*nod)];
		care[nod]=care[(2*nod)];
	}
}
int dmin[50000];
int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	int i,j;
	for(i=1;i<=m;i++){
		int a,b,c;
		f>>a>>b>>c;
		vec[a].pb(b);
		cost[a].pb(c);
		
		if(i<=n)
			dmin[i]=100000;
	}
	memset(aint,1,sizeof(aint));
	x = 0;
	poz = 1;
	inserare(1,1,n);
	dmin[1]=0;
	for(i=1;i<=n;i++){
		int y=care[1];
		
		for(j=0;j<vec[y].size();j++){
			if(dmin[vec[y][j]]>cost[y][j]+dmin[y]){
				dmin[vec[y][j]]=cost[y][j]+dmin[y];
				x=dmin[vec[y][j]];
				poz=vec[y][j];
				inserare(1,1,n);
			}
		}
		x = 2104324354;
		poz = y;
		inserare(1,1,n);
	}
	for(i=2;i<=n;i++){
		g<<dmin[i]<<" ";
	}
	return 0;
}