#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct edge{
int dr,c;} edg;
vector<struct edge> v[50003];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,x,dim;
int d[50003],heap[50003],Pos_in_heap[50003];
int left_node(int i)
{
    if ( i * 2 <= n )
        return (i*2);
    return 0;
}
int right_node(int i)
{
    if ( i * 2 + 1 <= n)
        return (i*2+1);
    return 0;
}
int father(int i)
{
    return i/2;
}
void change_pos(int a,int b)
{
    int temporary = Pos_in_heap[ a ];
    Pos_in_heap[ a ] = Pos_in_heap[ b ];
    Pos_in_heap[ b ] = temporary;
}
void update(int s,int t,int cost)
{
    int poz = Pos_in_heap[ t ];
    while( poz!=1 )
        if( d[ heap[ poz ] ] < d[ heap[ father(poz) ] ] )
        {
            change_pos( heap[ poz ] , heap[ father(poz) ] );
            swap( heap[poz], heap[ father(poz) ] );
            poz = father(poz);
        }
        else
            poz = 1;
}
int extract()
{
    int nod,pozmin,poz;
    change_pos(heap[1],heap[n]);
    swap( heap[ 1 ] ,heap[ n ] );
    nod = heap[ n ];
    if ( n == 1 )
    {
        n--;
        return nod;
    }
    else
    {
        n--;
        poz = 1;
        while( right_node(poz) || left_node(poz) )
            if( right_node(poz) && left_node(poz) )
            {
                pozmin=poz;
                if ( d[ heap[ left_node( poz ) ] ] < d[ heap[ pozmin ] ] )
                    pozmin = left_node(poz);
                if ( d[ heap[ right_node( poz ) ]  ] < d[ heap[ pozmin ] ] )
                    pozmin = right_node(poz);
                if( pozmin != poz)
                {
                    change_pos(heap[ pozmin ], heap[ poz ]);
                    swap(heap[ pozmin],heap[ poz ]);
                    poz = pozmin;
                }
                else
                    poz = n;
            }
            else
                if( left_node(poz) )
                    if (d[ heap[ left_node( poz ) ]  ] < d[ heap[ poz ] ])
                    {
                        change_pos( heap[ left_node(poz) ] , heap[ poz ] );
                         swap( heap[ left_node(poz) ] , heap[ poz ] );
                         poz = left_node(poz);
                    }
                    else
                        poz = n+1;
                else
                    if (d[ heap[ right_node( poz ) ] ]< d[ heap[ poz ] ])
                    {
                         change_pos( heap[ right_node(poz) ] , heap[ poz ] );
                         swap( heap[ right_node(poz) ] , heap[ poz ] );
                         poz = right_node(poz);
                    }
                    else
                        poz = n+1;
        return nod;
    }
}
void dijkstra_with_heap()
{
    int start;
    d [ 1 ] = 0;
    while ( n >= 0 )
    {
        start = extract();
        for ( auto it = v[start].begin() ; it != v[start].end() ; it++ )
            if ( d[ start ] + it -> c < d[ it->dr ] )
            {
                d[ it -> dr ] = d[ start ] + it -> c ;
                update( start , it -> dr , it -> c );
            }
    }
}
int main()
{
    int i;
    in>>n>>m;
    for ( i = 1 ; i <= n ; i ++ )
    {
        heap[ i ] = i ;
        Pos_in_heap[ i ] = i;
        d[ i ] = 1 << 30 ;
    }
    for( i = 1 ; i <= m ; i ++ )
    {
        in >>x >> edg.dr >> edg.c ;
        v[ x ].push_back( edg );
    }
    dim = n;
    dijkstra_with_heap();
    for( i = 2 ; i <= dim ; i ++ )
        if ( d[ i ] == 1<<30 )
            out << 0 << " " ;
        else
            out << d[ i ] << " " ;

    return 0;
}