#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>

#define NN 50009
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define oo 0x3f3f3f3f

const char iname[]="dijkstra.in";
const char oname[]="dijkstra.out";

using namespace std;
ofstream out(oname);

int n  ,  m;

vector< pair < int , int > > G[NN];
typedef vector< pair < int , int > >:: iterator IT;
vector<int>D;

priority_queue< pair < int , int > > Q;

void read();
void Dijkstra( int root );
void wrs();


int main()
{


    read();
    Dijkstra(1);
    wrs();


    return 0;


}


void read()
{

    ifstream in(iname);
    in >> n >> m;

    for( int x , y , cost ; m ; --m)
    {

        in >> x >> y >> cost;
        G[x].pb( mp( y , cost));
    }
}


void Dijkstra( int root )
{

    D.resize( n + 1 , oo );
    D[ root ] = 0;
    Q.push( mp ( 0 , root) );

    while( !Q.empty() )
    {

        int cost , nod;
        cost = -Q.top().f;
        nod = Q.top().s;


        Q.pop();

        for( int i = 0; i < G[nod].size(); ++i )
            if( D[ G[nod][i].f ]  > cost + G[nod][i].s )
            {

                D[G[nod][i].f ] = cost + G[nod][i].s ;
                Q.push( mp ( -D[G[nod][i].f] , G[nod][i].f));
            }

    }

}


void wrs()
{

    for( int i=2 ; i<=n ; i++)
        if ( D[i] == oo )
            out << 0 << " " ;
            else
            out << D[i] << " ";


}