#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;   
}