#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],poz[maxn],val[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 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);

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

   dijkstra(1);
   for(int i=2 ; i <= N ; i++)
     if(val[i] == inf)
        g<<0<<' ';
     else
        g<<val[i]<<' ';

   return 0;
}