#include <fstream.h>
#define INF 2000000000

typedef struct adjnod{
	int nod,val;
	adjnod *next;
}ADJ;
ADJ *adj[50001];

typedef struct{
	int index,value;
}HEAP;

unsigned int n;
long m;
unsigned int D[50001],viz[50001],hsize;
HEAP heap[50001];

void MinHeapify(HEAP v[],unsigned int sz,int i){
	int l=i*2;
	int r=i*2+1,smallest=0;
	if(l<=sz){
		if(v[i].value<v[l].value) smallest=i;
		else smallest=l;
	}
	if(r<=sz && v[r].value<v[smallest].value) smallest=r;

	if(smallest && smallest!=i){
		HEAP aux=v[smallest];
		v[smallest]=v[i];
		v[i]=aux;
		MinHeapify(v,sz,smallest);
	}
}

HEAP ExtractMinHeap(HEAP v[], unsigned int &sz){
	HEAP min=v[1];
	v[1]=v[sz];
	sz--;
	MinHeapify(v,sz,1);
	return min;
}

void BuildHeap(HEAP v[],unsigned int sz){
	for(int i=sz/2;i>0;i--) MinHeapify(v,sz,i);
}

void init(){
	ifstream f("dijkstra.in");
	f>>n>>m;
	int i,x,y,z;
	for(i=1;i<=m;i++){
		f>>x>>y>>z;
		ADJ *q=new ADJ;
		q->nod=y;
		q->val=z;
		q->next=adj[x];
		adj[x]=q;
	}
	f.close();
}

void Dijkstra(int start){
	int i;
	for(i=1;i<=n;i++){ D[i]=INF; heap[i].index=i; heap[i].value=INF; }
	D[start]=0;
	hsize=n;
	HEAP el;
	heap[start].value=0;
	BuildHeap(heap,hsize);
	ExtractMinHeap(heap,hsize);

	int curr=start;
	do{
		viz[curr]=1;
		if(D[curr]!=INF){
			ADJ *q=adj[curr];
			while(q){
				if(D[q->nod]>D[curr]+q->val && !viz[q->nod]){
					D[q->nod]=D[curr]+q->val;
					for(i=1;i<=n;i++)
						if(heap[i].index==q->nod){
							heap[i].value=D[curr]+q->val;
							BuildHeap(heap,hsize);
							break;
						}
				}
				q=q->next;
			}
		}
		el=ExtractMinHeap(heap,hsize);
	}while(curr=el.index);
}

void output(){
	ofstream g("dijkstra.out");	
	int i;
	for(i=1;i<=n;i++){
		if(D[i]==INF) g<<0<<" ";
		else g<<D[i]<<" ";
	}
	g.close();
}


int main(){
	init();
	Dijkstra(1);
	output();
	return 0;
}