#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 d[N];
const int D=(1<<16)-1; // folosesc pt modulo
int nh;

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;
    }
}
	
void bellman_ford()
{
    int i, j;

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

    d[1]=0;

    int Q[(1<<16)],p=0,q=0; // Q= coada circulara 
    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();
    bellman_ford();
    return 0;
}