#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define ll long long 
struct cell{
	ll index,value;
	
	
};
typedef struct nod{
	ll val,cost;
	nod* next;
	
}*graf;
const ll inf=LONG_LONG_MAX-100;
graf lda[400001];
cell heap[400001];
ll N,drum[400001];
ll link[400001];//index la nod->pozitia in heap
//map <ll,pair<ll,ll> > edges;//index la nod->nodul de la care vine legatura + costul
void add(graf &a,ll val,ll cost){
	graf b=new nod;
	b->val=val;
	b->cost=cost;
	b->next=a;
	a=b;
	
	
}

void sift(ll k){
	ll son;
	do {
		son=0;
		if (2*k<=N) {
		son=2*k;
		if (2*k+1<=N&&heap[2*k+1].value<heap[2*k].value)son =2*k+1;
		if (heap[son].value>=heap[k].value) son=0;
		
	}
		if (son) swap(link[heap[k].index],link[heap[son].index]),swap(heap[k],heap[son]),k=son;
	}while(son);
	
	
}

void perlocate(ll k){
	cell key=heap[k];
	while(k>1&&key.value<heap[k/2].value){
		swap(heap[k],heap[k/2]);
		swap(link[heap[k].index],link[heap[k/2].index]);
		k/=2;
	}
		//heap[k]=key;
}


void cut(ll k){
	link[heap[k].index]=-1;
	link[heap[N].index]=1;
	heap[k]=heap[N];

	--N;
	//if (k>1&&heap[k]>heap[k/2]) perlocate(k);
    sift(k);
	
}
void insert(cell key){
	heap[++N]=key;
	link[heap[N].index]=N;
	perlocate(N);
	
}
void update(ll k,ll newv){
	heap[k].value=newv;
	perlocate(k);
	
}


int main(){
	ll n,m;
	fin >>n>>m;
	for(ll i=1;i<=m;i++){
		ll a,b,c;
		fin>>a>>b>>c;
		add(lda[a],b,c);
		//add(lda[b],a,c);
	}
	//cout <<inf<<endl;
	cell x;
	x.index=1;
	x.value=0;
	insert(x);
	x.value=inf;
	for(ll i=2;i<=n;i++){
		x.index=i;
		insert(x);
	}
	while(N){
		 cell source=heap[1];
		 cut(1);
		 drum[source.index]=source.value;
		 for(graf it=lda[source.index];it!=NULL;it=it->next)
			 if (it->cost+drum[source.index]<heap[link[it->val]].value&&link[it->val]!=-1) {
				 ll op=it->cost+drum[source.index];
				 update(link[it->val],op);
			}
		
	}
	for(int i=2;i<=n;i++)  if (drum[i]<0||drum[i]>1e10) fout <<"0 ";
	 else fout <<drum[i]<<" ";
	return 0;
}