#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

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;

    for(i=1;i<=n;++i) H[i]=i,poz[i]=i;

    for(i=n/2;i;--i) downheap(i); // construiesc heapul O(n)
    nh=n;

    nod *it;
    int u;

    while(nh)
    {
	u=H[1];
	swap(1, nh--);
	downheap(1);

	for(it=a[u]; it; it=it->next)
	    if(d[u] + it->cost < d[it->x])
	    {
		d[it->x]=d[u] + it->cost;
	        upheap(poz[it->x]);
	    }
    }	

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


}

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