#include <cstdio>
const int maxn = 50002;
const int oo = 1 << 30;

FILE *f = fopen("dijkstra.in","r");
FILE *g = fopen("dijkstra.out","w");

struct graf
{
    int vcn, cost;
    graf *urm;
};

int n, m;
graf *a[maxn];
int d[maxn], h[maxn], w[maxn], k=0;

void adg(int x, int y, int cost)
{
    graf *q = new graf;
    q->vcn = y;
    q->cost = cost;
    q->urm = a[x];
    a[x] = q;
}

void read()
{
    fscanf(f, "%d %d", &n, &m);

    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(f, "%d %d %d", &x, &y, &z);
        adg(x, y, z);
    }
}

void urcam(int fiu)
{
    int tata,nod=h[fiu],niv=-1,node;
    int dist=d[nod];

    while ( fiu > 1 )
    {
        tata = fiu >> 1;
        node=h[tata];

        if ( d[ h[tata] ] > dist )
        {
            h[fiu]=node;
            w[node]=fiu;
            fiu=tata;
        }
        else
        {
            niv=fiu;
            fiu = 1;
        }
    }
    if(niv>0)
        fiu=niv;
    h[fiu]=nod;
    w[nod]=fiu;
}


void coboram()
{
    int x=h[1],tata=1,fiu=2;

    while(fiu<=n)
    {
        if(fiu<n)
            if(d[h[fiu+1]]<d[h[fiu]])
                fiu=fiu+1;
        if(x>d[h[fiu]])
        {
            h[tata]=h[fiu];
            w[ h[tata] ] = tata;
            tata=fiu;
            fiu*=2;
        }
        else
        {
            fiu=n+1;
        }
    }
    h[tata]=x;
    w[x]=tata;
}


void dijkstra()
{
    for ( int i = 2; i <= n; ++i )
        d[i] = oo, w[i] = -1;
    w[1] = 1;

    h[++k] = 1;

    while ( k )
    {
        int mn = h[1];
        w[mn]=-1;

        h[1]=h[k];
        w[ h[1] ] = 1;
        --k;

        coboram();

        graf *q = a[mn];

        while ( q )
        {
            int vecin=q->vcn;
            if ( d[vecin] > d[mn] + q->cost )
            {
                d[vecin] = d[mn] + q->cost;

                if ( w[vecin] != -1 )
                {
                    urcam( w[vecin] );
                }

                else
                {
                    h[++k] = vecin;
                    w[vecin ] = k;
                    urcam( k );
                }
            }
            q = q->urm;
        }
    }
}

int main()
{
    read();
    dijkstra();

    for ( int i = 2; i <= n; ++i )
        fprintf(g, "%d ", d[i] == oo ? 0 : d[i]);
    fprintf(g, "\n");

    return 0;
}