#include <bits/stdc++.h>

using namespace std;

ifstream fin( ".in" );
ofstream fout( ".out" );

int i,j,n,m,k,x,y,c,ans[100010];
vector<pair<int,int> > G[100010];
priority_queue< pair<int,int> , vector< pair<int,int> > , greater<pair<int,int> > > heap;

const int inf = 1000000000;

int main()
{
    fin>>n>>m;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y>>c;
        G[ x ].push_back( { y , c } );
    }
    for( i = 1 ; i <= n ; i++ )
    {
        ans[ i ] = inf;
    }

    heap.push( { 0 , 1 } );
    while( heap.size() )
    {
        pair< int , int > cur = heap.top();
        ans[ cur.second ] = cur.first;
        for( auto it : G[ cur.second ] )
        {
            if( ans[ it.first ] == inf )
            {
                heap.push( { ans[ cur.second ] + it.second , it.first } );
            }
        }
        while( heap.size() && ans[ heap.top().second ] != inf )
        {
            heap.pop();
        }
    }

    for( i = 2 ; i <= n ; i++ )
    {
        fout<<ans[ i ]<<' ';
    }

    return 0;
}