#include <cstdio>
#include <string>
#include <fstream>
#define maxn 50001
#define oo 0x3f3f3f3f
using namespace std;

struct nd { int x,c; nd *n;};

nd *a[maxn];
int H[3*maxn][2];
int d[maxn];
int n;

void read()
{
    int m, p, q, c;
    nd *t;
    ifstream f("dijkstra.in");
    f>>n>>m;
    while(m--)
    {
	f>>p>>q>>c;
	t=new nd;
	t->x=q;
	t->c=c;
	t->n=a[p];
	a[p]=t;
    }
}

inline void build(int n, int l, int r)
{
    if(l>=r) { H[n][0]=l, H[n][1]=d[l];return;}

    int m=(l+r)>>1, st=n<<1, dr=st+1;

    build(st, l, m);
    build(dr, m+1, r);
    if(H[st][1]<H[dr][1]) H[n][0]=H[st][0], H[n][1]=H[st][1];
    else H[n][0]=H[dr][0], H[n][1]=H[dr][1];
}


inline void update(int n, int l, int r, int p, int v)
{
    if(l>=r){ H[n][0]=p; H[n][1]=v;return;}

    int m=(l+r)>>1, st=n<<1, dr=st+1;

    if(p<=m) update(st, l, m, p,v);
    else update(dr, m+1, r, p, v);

    if(H[st][1]<H[dr][1])  H[n][1]=H[st][1], H[n][0]=H[st][0];
	else H[n][1]=H[dr][1], H[n][0]=H[dr][0];
}


void solve()
{
    int i,u,mn;
    nd *p;
    memset(d, oo, sizeof(d));
    d[1]=0;
    build(1, 1, n);
    
    while(1)
    {
	u=H[1][0];
	mn=H[1][1];
	if(mn==oo) break;
	update(1,1, n,u, oo);

	for(p=a[u]; p; p=p->n)
	    if(d[u]+ p->c < d[p->x])
	    {
		d[p->x] = d[u] + p->c;
		update(1,1, n, p->x, d[p->x]);
	    }
    }

    for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0;

    ofstream g("dijkstra.out");
    for(i=2;i<=n;++i)g<<d[i]<<" ";
    g<<"\n";

}


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