#include <cstdio>      
     
const int maxn = 50001;      
const int inf = 1 << 30;      
     
FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");      
     
struct graf      
{      
    int nod, cost;      
    graf *next;      
};      
     
int n, m;      
graf *a[maxn];      
int d[maxn], h[maxn], poz[maxn], k;      
     
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()      
{      
    fscanf(in, "%d %d", &n, &m);      
     
    int x, y, z;      
    for ( int i = 1; i <= m; ++i )      
    {      
        fscanf(in, "%d %d %d", &x, &y, &z);      
        add(x, y, z);      
    }      
}      
     
void swap(int x, int y)      
{      
    int t = h[x];      
    h[x] = h[y];      
    h[y] = t;      
}      
     
void upheap(int what)      
{      
    int tata;      
    while ( what > 1 )      
    {      
        tata = what >> 1;      
     
        if ( d[ h[tata] ] > d[ h[what] ] )      
        {      
            poz[ h[what] ] = tata;      
            poz[ h[tata] ] = what;      
     
            swap(tata, what);      
     
            what = tata;      
        }      
        else     
            what = 1;      
    }      
}      
     
void downheap(int what)      
{      
    int f;      
    while ( what <= k )      
    {      
        f = what;      
        if ( (what<<1) <= k )      
        {      
            f = what << 1;      
            if ( f + 1 <= k )      
                if ( d[ h[f + 1] ] < d[ h[f] ] )      
                    ++f;      
        }      
        else     
            return;      
     
        if ( d[ h[what] ] > d[ h[f] ] )      
        {      
            poz[ h[what] ] = f;      
            poz[ h[f] ] = what;      
     
            swap(what, f);      
     
            what = f;      
        }      
        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 min = h[1];      
        swap(1, k);      
        poz[ h[1] ] = 1;      
        --k;      
     
        downheap(1);      
     
        graf *q = a[min];      
     
        while ( q )      
        {      
            if ( d[q->nod] > d[min] + q->cost )      
            {      
                d[q->nod] = d[min] + 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();      
     
    for ( int i = 2; i <= n; ++i )      
        fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);      
    fprintf(out, "\n");      
     
    return 0;      
}