#include<fstream>
#define MAX 50001
#define inf 1<<30
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct graf {
int node,cost;
graf *next;
}*a[MAX];
int n,m;
int h[MAX],poz[MAX],d[MAX] ,num;
void add(int origin,int destination, int cost)
{
	graf *c=new graf;
	c->node=destination;
	c->cost=cost;
	c->next=a[origin];
	a[origin]=c;
}
void read() {
int w,b,c;
f>>n>>m;
 for (int i=1; i<=m; i++)
 {	f>>w>>b>>c; add(w,b,c);}
 
}
void swap(int a, int b){ int t=h[a]; h[a]=h[b]; h[b]=t;}
void upheap(int k){
int father;
while (k>1 )
{
	father=k>>1;
	if (h[k]<h[father])
	{
		poz[h[k]]=father;
		poz[h[father]]=k;
		swap (k,father);
		k=father;
	}
	else k=1;
 }
}
void downheap(int what)
{
    int f;
    while ( what <= num )
    {
        f = what;
        if ( (what<<1) <= num )
        {
            f = what << 1;
            if ( f + 1 <= num )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;
 
        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;
 
            swap(what, f);
 
            what = f;
        }
        else
            return;
    }
}
void djikstraHeap(){
for (int i=2; i<=n; i++) {d[i]=inf; poz[i]=-1;}
d[1]=0; poz[1]=1;
h[++num]=1;
	while (num){
		int min=h[1];
		swap(1,num);
		poz[h[1]]=1;
		--num;
		downheap(1);
		graf *q=a[min];
		while (q){
			if (d[q->node]>d[min]+q->cost){
				d[q->node]=d[min]+q->cost;
				if (poz[q->node]!=-1)
					upheap(poz[q->node]);
				else
				{ h[++num]=q->node;
				  poz[q->node]=num;
				  upheap(num);
				}	
			}
		q=q->next;
		}
	}
}
int main()
{
	read();
	djikstraHeap();
	for (int i=2; i<=n; i++)
		if (d[i]!=inf) g<<d[i]<<" "; else g<<0<<" ";
	f.close();
	g.close();
	return 0;	
}