using namespace std;
#define MAX 50005
#define pb push_back
#include<cstdio>
#include<fstream>
#include<vector>
#define INFINIT 2000000000
struct varf{
    int c,i;
};
inline int father(int k){
    return k/2;}
inline int left_son(int k){
    return k*2;}
inline int right_son(int k){
    return k*2+1;}

vector<varf > G[MAX];
vector<int> d, t, h, poz;
int na,n;

void cerne(int k)
{
    int son;
    do
    {
        son=0;
        if(left_son(k)<=na)
        {
            son=left_son(k);
            if(right_son(k)<=na && d[h[right_son(k)]]<d[h[son]])
                son=right_son(k);
            if(d[h[son]]>d[h[k]])
                son=0;
        }
        if(son)
        {
            swap(h[k],h[son]);
            swap(poz[h[k]],poz[h[k]]);
            k=son;
        }
    }while(son);
}

void promoveaza(int k)
{
    while(k>1 && d[h[k]]<d[h[father(k)]])
    {
        swap(h[k],h[father(k)]);
        swap(poz[h[k]],poz[h[father(k)]]);
        k=father(k);
    }
}

void init(int sursa)
{
    int i;
    for(i=0;i<=n;i++)
        d[i]=INFINIT, t[i]=-1, h[i]=i, poz[i]=i;
    na=n;
    d[sursa]=0,t[sursa]=0;
    h[poz[sursa]]=h[na--];
    poz[h[sursa]]=sursa;
    cerne(sursa);
    for(i=0;i<G[sursa].size();i++)
        if(d[G[sursa][i].i]>d[sursa]+G[sursa][i].c)
        {
            d[G[sursa][i].i]=d[sursa]+G[sursa][i].c;
            t[G[sursa][i].i]=sursa;
            promoveaza(poz[G[sursa][i].i]);
        }
}

void dijkstra(int sursa)
{
    init(sursa);
    for(int kk=1;kk<n;kk++)
    {
        int pmin=h[1];
        if(d[pmin]==INFINIT)
            break;
        h[1]=h[na--];
        poz[h[1]]=1;
        cerne(1);
        for(int i=0;i<G[pmin].size();i++)
            if(d[pmin]+G[pmin][i].c<d[G[pmin][i].i])
            {
                d[G[pmin][i].i]=d[pmin]+G[pmin][i].c;
                t[G[pmin][i].i]=pmin;
                promoveaza(poz[G[pmin][i].i]);
            }
    }
}

int main()
{
    int m,i;
    ifstream fin("dijkstra.in");
    freopen("dijkstra.out", "w", stdout);
    fin>>n>>m;
    d.reserve(n+1);
    h.reserve(n+1);
    poz.reserve(n+1);
    t.reserve(n+1);
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        varf f;
        f.i=y;
        f.c=c;
        G[x].pb(f);
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]==INFINIT)
            printf("0 ");
        else
            printf("%d ", d[i]);
    }
    return 0;
}