using namespace std;
#include <fstream>
#include <string>
#define maxn 50001
#define T(i) ((i)>>1)
#define L(i) ((i)<<1)
#define R(i) (((i)<<1)|1)
#define oo 0x3f3f3f3f

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

nd *a[maxn];
int n;
int d[maxn], poz[maxn];
int H[maxn];
int nh;

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

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

inline void down(int i)
{
    int m=i;
    if(L(i)<=nh)
	if(d[H[L(i)]]<d[H[i]]) m=L(i);
    if(R(i)<=nh)
	if(d[H[R(i)]]<d[H[m]]) m=R(i);
    if(m!=i) swap(i,m), down(m);
}

void solve()
{
    nd *it;
    int i,u;
    nh=n;
    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) down(i);

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

	for(it=a[u]; it ; it=it->n)
	    if(d[u] + it->c < d[it->x])
	    {
		d[it->x]=d[u]+it->c;
		up(poz[it->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";


}

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

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