#include <fstream>
#include <set>
#include <vector>

using namespace std;

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

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} );
        //G[ y ].push_back( {x,c} );
    }
    for( i = 0 ; i <= n ; i++ )
        min_dist[ i ] = oo;

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

    while( muchii_active.size() )
    {
        c = (*muchii_active.begin()).first;
        x = (*muchii_active.begin()).second;

        muchii_active.erase( muchii_active.begin() );

        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.insert( { 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;
}