#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define inf 999999999
struct nod
{
    int info,cost;
    nod* urm;
}*pt[60000];
int N,M,h,heap[60000],poz[60000],val[60000],tata[60000];

void InserareNod(nod* &point,int val,int ct)
{
   nod* cap = new nod;
   cap->info = val;
   cap->cost = ct;
   cap->urm = point;
   point = cap;
}

inline int father(int nod) {
    return nod / 2;
}
inline int left_son(int nod) {
    return nod * 2;
}
inline int right_son(int nod) {
    return nod * 2 + 1;
}

void swap_nod(int x,int y)
{
    swap( heap[poz[x]],heap[poz[y]] );
    swap( poz[x],poz[y] );
}

void up(int nod)
{
     int ok = 0;

     while( nod > 1 && ok == 0 )
     {
        if( val[ heap[ nod ] ] >= val[ heap[ father(nod) ] ] )
            ok = 1;
        else
        {
            swap_nod( heap[ nod ],heap[ father(nod) ] );
            nod = father(nod);
        }
     }
}

void down(int nod)
{
    int ok = 0;

    while( nod * 2 <= h && ok == 0 )
    {
        if( val[ heap[ nod ] ] <= val[ heap[ left_son(nod) ] ] && val[ heap[ nod ] ] <= val[ heap[ right_son(nod) ] ] )
            ok = 1;
        else
        if( val[ heap[ nod ] ] <= val[ heap[ left_son(nod) ] ] && right_son(nod) > h  )
            ok = 1;
        else
        {
            if( val[ heap[ nod ] ] > val[ heap[ left_son(nod) ] ] && ( val[ heap[ left_son(nod) ] ] <= val[ heap[ right_son(nod) ] ] || right_son(nod) > h ) )
            {
                swap_nod( heap[ nod ],heap[ left_son(nod) ] );
                nod = left_son(nod);
            }
            else
            if( val[ heap[ nod ] ] > val[ heap[ right_son(nod) ] ] && val[ heap[ left_son(nod) ] ] >= val[ heap[ right_son(nod) ] ] )
            {
                swap_nod( heap[ nod ],heap[ right_son(nod) ] );
                nod = right_son(nod);
            }
        }
    }
}

void Eliminare(int nod)
{
    int aux = heap[h];
    poz[ aux ] = poz[ nod ];
    heap[ poz[ nod ] ] = aux;
    poz[ nod ] = 0;
    heap[h] = 0;
    h--;

    up( poz[ aux ] );
    down( poz[ aux ] );
}

void dijkstra(int xp)
{
    int u;
    for(int i = 1 ; i <= N ; i++)
    {
        val[i] = inf;
        heap[i] = i;
        poz[i] = i;
    }
    h = N;
    val[xp] = 0;
    swap_nod(xp,heap[1]);

    while( h!=0 )
    {
        u = heap[1];
        Eliminare(u);

        nod* cap = pt[u];

        while( cap != NULL )
        {
            int y = cap->info;
            int ct = cap->cost;

            if( val[y] > val[u] + ct )
            {
                val[y] = val[u] + ct;
                tata[y] = u;
                up(poz[y]);
            }

            cap = cap->urm;
        }
    }
}

int main()
{
    int a,b,c;
    f>>N>>M;
    for(int i = 1 ; i <= N ; i++)
        pt[i] = NULL;

    for(int i=1 ; i <= M ; i++)
    {
        f>>a>>b>>c;
        InserareNod(pt[a],b,c);
        InserareNod(pt[b],a,c);
    }

    dijkstra(1);
    for(int i = 2 ; i <= N ; i++)
        g<<val[i]<<' ';
}