#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <ctime>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream ff("dijkstra.in");
ofstream gg("dijkstra.out");

#define max 50001
#define inf 0xffffff
struct per{int x,v; per(int x0,int v0){x=x0;v=v0;}};
vector<per> vv[max];
int n, m, k, pp[max], dd[max];
struct hp{
	int x, v;
	hp(int x0=0,int v0=0,int p0=0){ x=x0;v=v0;pp[x]=p0; }
} hh[max];
bool operator<(hp a, hp b){ return a.v<b.v; }
void swp(int t, int f){ swap(hh[t], hh[f]); swap(pp[hh[t].x], pp[hh[f].x]); }

void add(int x, int v){
	int t, f;
	if(pp[x]==0){
		k++;
		hh[k]=hp(x,v,k);
	} else hh[pp[x]].v=v;
	f=pp[x]; t=f/2;
	while(t>0 && hh[f]<hh[t]){
		swp(t, f);
		f=t; t=f/2;
	}
}

void del(int x){
	int t,f;
	swp(x, k--);
	t=x; f=2*t;
	if(f<k && hh[f+1]<hh[f])f++;
	while(f<=k && hh[f]<hh[t]){
		swp(t, f);
		t=f; f=2*t;
		if(f<k && hh[f+1]<hh[f])f++;
	}
}

void djk(){
	int x,y,c,l;
	for(int i=1;i<=n;i++) dd[i]=inf;
	dd[1]=0;
	add(1,0);
	while(k>0){
		x=hh[1].x; del(pp[x]);
		l=vv[x].size();
		for(int i=0;i<l;i++){
			y=vv[x][i].x;
			c=vv[x][i].v;
			if(dd[y]>dd[x]+c){
				dd[y]=dd[x]+c;
				add(y, dd[y]);
			}
		}
	}
	for(int i=2;i<=n;i++) gg << (dd[i]==inf?0:dd[i]) << " ";
}

int main(){
	int a,b,c;
	ff >> n >> m;
	for(int i=0;i<m;i++){
		ff >> a >> b >> c;
		vv[a].push_back(per(b,c));
	}
	djk();
	return 0;
}