#include <cstdio>
#include <string>
#define T ((i)>>1)  // T=tata, L=left, R=right
#define L ((i)<<1)
#define R (L+1)
#define N 50001
#define oo 0x3f3f3f3f // infinit

struct nod { int x, cost; nod *next;};

nod *a[N];
int n, m;
int H[N], poz[N], d[N];
// H=heap, poz=pozitia in heap, d=distanta minima
int nh; // nh=nr elemenete din heap

const int D=(1<<17)-1;

void read()
{
    freopen("dijkstra.in","r",stdin);

    scanf("%d %d\n", &n, &m);

    int p, q, c;

    while(m--)
    {
	scanf("%d %d %d\n", &p, &q, &c);
	nod *t=new nod;
	t->x=q;
	t->cost=c;
	t->next=a[p];
	a[p]=t;
    }
}

inline void swap(int i, int j)
{
    int aux=H[i];
    H[i]=H[j];
    H[j]=aux;
    poz[H[i]]=i;
    poz[H[j]]=j;
}

inline void upheap(int i)
{
    if(i<=1) return;
    if(d[H[i]] < d[H[T]]) swap(i, T),upheap(T);
}

inline void downheap(int i)
{
    int min=i;

    if(L<=nh)
	if(d[H[min]] > d[H[L]]) min=L;
    if(R<=nh)
	if(d[H[min]] > d[H[R]]) min=R;

    if(i!=min) swap(i,min), downheap(min);
}


	
void dijkstra()
{
    int i, j;

    memset(d, oo, sizeof(d));
    d[1]=0;


    bool inq[N];
    memset(inq, 0, sizeof(inq));

    int Q[(1<<17)],p=0,q=0;
    nh=1;
    Q[0]=1;

    nod *it;
    int u;
    

    while(nh)
    {
	u=Q[p];
	++p;
	p&=D;
	--nh;
	
	for(it=a[u]; it; it=it->next)
	    if(d[u] + it->cost < d[it->x])
	    {
		d[it->x]=d[u] + it->cost;
	        ++q;
		q&=D;
		Q[q]=it->x;
		++nh;
	    }

    }	

    for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0;
   freopen("dijkstra.out","w",stdout);
   for(i=2;i<=n;++i)printf("%d ", d[i]);
   printf("\n");


}

int main()
{
    
    read();
    dijkstra();
    return 0;
}