#include <cstdio>
using namespace std;

#define NMAX 50001
#define inf 1 << 30

struct graf{

    int nod, cost;
    graf *next;
};

graf *a[NMAX];
int n,m,k;
int d[NMAX], h[NMAX], poz[NMAX];

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}

void read()
{
    freopen("dijkstra.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d%d%d", &x, &y, &c);
        add(x , y , c);
    }
}

void swapp(int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void upheap(int what)
{
    int tata;
    while(what > 1)
    {
        tata = what>>1;
        if (d[ h[tata] ] > d[ h[what] ])
        {
            poz[ h[tata] ] = what;
            poz[ h[what] ] = tata;

            swapp(tata, what);
            what = tata;
        }
        else what = 1;
    }
}

void downheap(int what)
{
    int fiu;
    while(what <= k)
    {
        fiu = what;
        if ( (what << 1) <= k)
        {
            fiu = what << 1;
            if (fiu + 1 <= k)
                if (d[ h[fiu + 1] ] < d[ h[fiu] ]) ++fiu;
        }
        else return;

        if (d[ h[what] ] > d[ h[fiu] ])
        {
            poz[ h[what] ] = fiu;
            poz[ h[fiu] ] = what;

            swapp(what, fiu);
            what = fiu;
        }
        else return;
    }
}

void dijkstra_heap()
{
    for(int i = 2; i <= n; i++)
        d[i] = inf, poz[i] = -1;
    poz[1] = 1;    h[++k] = 1;
    while( k )
    {
        int minn = h[1];
        swapp(1, k);
        poz[ h[1] ] = 1;
        --k;

        downheap(1);

        graf *q = a[minn];

        while ( q )
        {
            if (d[ q->nod ] > d[minn] + q->cost)
            {
                d[ q->nod ] = d[minn] + q->cost;
                if (poz[ q->nod ] != -1)
                    upheap(poz[ q->nod ]);
                else{
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
                    upheap(k);
                }
            }

            q = q -> next;
        }
    }
}

int main()
{
    read();
    dijkstra_heap();

    freopen("dijkstra.out", "w" , stdout);

    for(int i=2;i<=n; i++)
        printf("%d ", d[i] == inf ? 0 : d[i]);
    printf("\n");
}