#include <bits/stdc++.h>

using namespace std;

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

void sift(int k){
	int 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(int 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(int 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(int k,int newv){
	heap[k].value=newv;
	perlocate(k);
	
}


int main(){
	int n,m;
	fin >>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		fin>>a>>b>>c;
		add(lda[a],b,c);
		//add(lda[b],a,c);
	}
	cell x;
	x.index=1;
	x.value=0;
	insert(x);
	x.value=inf;
	for(int 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<heap[link[it->val]].value) {
				 update(link[it->val],it->cost+drum[source.index]);
				 //edges[it->val].first=source.index;
				 //edges[it->val].second=it->cost;
			}
		
	}
	
	for(int i=2;i<=n;i++) if (drum[i]==inf) fout <<"0 ";
	else  fout <<drum[i]<<" ";
	return 0;
}