#include<bits/stdc++.h>


#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"


#define oo ((1LL<<31)-1)
#define MAXN 50001

using namespace std;

int nodes,
    edges;

vector<pair<int,int > > Graph[ MAXN ];
int distMin[ MAXN ];

queue<int> Queue;
bitset<MAXN> inQueue;

void read() {

     int x,
         y,
         cost;

     ifstream fin(FIN);
     fin>>nodes>>edges;
     while(edges--){
           fin>>x>>y>>cost;
           Graph[ x ].push_back({y,cost});
            //push in vector
     }
     fin.close();
};

void Dijkstra() {

    //initializare dist minima cu "infinit"
     for(int i = 2; i <= nodes; i++)
        distMin[ i ] = oo;

     //adaug primul nod
     distMin[ 1 ] = 0;
     Queue.push( 1 );
     inQueue[ 1 ] = true;

     while( !Queue.empty() ) {

            //selectez primul nod din coada
            int node = Queue.front();
            Queue.pop();
            inQueue[ node ] = false;
            //si il elimin

            //pt fiecare nod din graf
            for(auto it : Graph[ node ]) {
                //dist din de la fiecare nod > dist de la nod + cost nodului precedent
                if(distMin[ it.first ] > distMin[ node ] + it.second) {
                  //dist min din nod
                   distMin[ it.first ] = distMin[ node ] + it.second;

                   if(!inQueue[ it.first ]) {

                       Queue.push( it.first );
                       inQueue[ it.first ] = true;
                   }
                }
            }
     }
};


void write() {

     ofstream fout(FOUT);

     for(int i = 2; i <= nodes; i++)

         (distMin[ i ] < oo) ? fout<<distMin[ i ]<<" " : fout<<0<<" ";

     fout.close();
};


int main() {

 read();
 Dijkstra();
 write();

 return(0);
};