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