#include <fstream>
#include <algorithm>
using namespace std;

#define maxn 50001
int inf=1<<30;

typedef struct graf{
	int nod,cost;
	graf *next;};

graf *y[maxn];
int d[maxn],heap[maxn],n,nh,m,pos[maxn],viz[maxn];

void sw(int a,int b){
	swap(heap[a],heap[b]);
	pos[heap[a]]=a;
	pos[heap[b]]=b;}

void push(int k){
	while(k/2&&d[heap[k]]<d[heap[k/2]]){
		sw(k,k/2);
		k=k/2;}}

void sift(int k){
	int son;
	do{
		son=0;
		if(k*2<=nh)
			son=k*2;
		if(k*2+1<=nh&&d[heap[k*2]]>d[heap[k*2+1]])
			son=k*2+1;
		if(d[heap[son]]>d[heap[k]])
			son=0;
		if(son){
			sw(k,son);
			k=son;}}
	while(son);}

void pop(int k){
	sw(k,nh);
	nh--;
	push(k);
	sift(k);}

void dijkstra(int k){
	int nod,cost;
	viz[k]=1;
	pop(pos[k]);
	graf *q;
	q=y[k];
	while(q){
		nod=q->nod;
		cost=q->cost;
		if(viz[nod]==0&&d[k]+cost<d[nod]){
			d[nod]=d[k]+cost;
			nh++;
			heap[nh]=nod;
			pos[nod]=nh;
			push(nh);}
		q=q->next;}
	if(nh)
		dijkstra(heap[1]);}


int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	int i,a,b,c;
	graf *q;
	for(i=1;i<=m;i++){
		f>>a>>b>>c;
		q=new graf;
		q->nod=b;
		q->cost=c;
		q->next=y[a];
		y[a]=q;}
	for(i=2;i<=n;i++)
		d[i]=inf;
    d[1]=0;
	nh=1;
	heap[1]=1;
	pos[1]=1;
	dijkstra(1);
	for(i=2;i<=n;i++)
		if(d[i]==inf)
			g<<0<<" ";
		else g<<d[i]<<" ";
	f.close();
	g.close();
	return 0;}