#include <cstdio>
#include <fstream>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int maxn = 50005;
const int inf = 1 << 30;
struct graf {int nod, cost; graf *next;};
graf *a[maxn];
int n,m,d[maxn],h[maxn],poz[maxn],k;
/// D e vectorul de cost.
void add(int x, int y, int cost)
{
    graf *q = new graf;
    q->nod = y,q->cost = cost,q->next = a[x],a[x] = q;
}
void read()
{
    cin>>n>>m;
    int x,y,z;
    while(cin>>x>>y>>z) add(x, y, z);
    for ( int i = 1; i <= n; ++i ) d[i] = inf, poz[i] = -1;
}
void upheap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;/// :2
        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;
            int t = h[tata]; h[tata] = h[what]; h[what] = t;
            what = tata;
        }
        else what = 1;
    }
}
void downheap(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        int r=what<<1;

        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;
            int t = h[what]; h[what] = h[f]; h[f] = t;
            what = f;
        }
        else return;
    }
}
void dijkstra_heap(int st)
{
    d[st]=0,poz[st] = 1,h[++k] = st;
    while ( k )
    {
        int min = h[1];
        int t = h[1]; h[1] = h[k]; h[k] = t; /// pune minimul la finalul vectorului h.
        --k; /// sterge ultimul element(minimul)
        poz[ h[1] ] = 1;
        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(1);
    for ( int i = 2; i <= n; ++i )
        if(d[i]!=inf) cout<<d[i]<<' ';
        else cout<<0<<' ';
}