#include <fstream>
#include <queue>
#include <vector>

using namespace std;

priority_queue < pair<int,int> > muchii_active;
vector < pair<int,int> > G[50010];
int n,m,min_dist[50010],i,j,x,y,c,oo=20000000,use[50010],p;

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

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

    min_dist[ 1 ] = 0;
    muchii_active.push( {0,1} );

    while( muchii_active.size() )
    {

        while( use[ (muchii_active.top()).second ] == 1 && muchii_active.size() )
            muchii_active.pop();
        if( muchii_active.empty() )
            break;

        c = (muchii_active.top()).first;
        x = (muchii_active.top()).second;
        use[ x ] = 1;

        muchii_active.pop();

        for( vector< pair<int,int> >::iterator it = G[ x ].begin() ; it != G[ x ].end() ; it++ )
        {
            if( min_dist[ (*it).first ] > c + (*it).second )
            {
                //muchii_active.erase( { min_dist[ (*it).first ] , (*it).first } );
                muchii_active.push( { c + (*it).second , (*it).first } );
                min_dist[ (*it).first ] = c + (*it).second;
            }
        }
    }
    for( i = 2 ; i <= n ; i++ )
        fout<<(min_dist[ i ]!=oo?min_dist[ i ]:0)<<' ';

return 0;
}