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

const int maxn = 50001;
const int inf = 1 << 30;
struct graf
{
    int info,cost;
    graf* urm;
}*pt[maxn];
int N,M,h,heap[maxn],val[maxn],poz[maxn];

void InserareGraf(graf* &point,int val,int ct)
{
   graf* cap = new graf;
   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 up(int nod)
{
     int aux1,aux2,ok = 0;

     while( nod > 1 && ok == 0 )
     {
        if( val[ heap[ nod ] ] >= val[ heap[ father(nod) ] ] )
            ok = 1;
        else
        {
            aux1 = heap[ father(nod) ];
            aux2 = heap[ nod ];

            heap[ nod ] = aux1;
            heap[ father(nod) ] = aux2;

            poz[ aux1 ] = nod;
            poz[ aux2 ] = father(nod);

            nod = father(nod);
        }
     }
}

void down(int nod)
{
    int aux1,aux2,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 ) )
            {
                aux1 = heap[ left_son(nod) ];
                aux2 = heap[ nod ];

                heap[ nod ] = aux1;
                heap[ left_son(nod) ] = aux2;

                poz[ aux1 ] = nod;
                poz[ aux2 ] = 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) ] ] )
            {
                aux1 = heap[ right_son(nod) ];
                aux2 = heap[ nod ];

                heap[ nod ] = aux1;
                heap[ right_son(nod) ] = aux2;

                poz[ aux1 ] = nod;
                poz[ aux2 ] = 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;

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

        graf* 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;
                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;
        InserareGraf(pt[a],b,c);
        InserareGraf(pt[b],a,c);
    }

    dijkstra(1);

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

    return 0;
}