#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

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

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

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

    pq.push( {0,1} );
    while( pq.size() )
    {
        use[ pq.top().s ] = 1;
        ans[ pq.top().s ] = pq.top().f;

        for( auto it : G[ pq.top().s ] )
            if( !use[ it.f ] )
                pq.push( { pq.top().f + it.s , it.f } );

        while( pq.size() && use[ pq.top().s ] ) pq.pop();
    }

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


return 0;
}