/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <fstream>
#include<queue>
#include<climits>
#include<functional>
#include<vector>
#include<algorithm>
#include<map>
using namespace std ;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int main()
{
    map<pair<int,int> , int > cost ; 
      int n , x , y , c , m  ;
        cin>>n>>m;
          vector<vector<int> > adj(n+1);
           for(int i =  1 ; i <= m ; i ++ ){
                 cin>>x;
                  cin>>y;
                  cin>>c;
                cost[{x,y}] = c ; 
               adj[x].push_back(y);
               
           }
                priority_queue<pair<int,int> ,vector<pair<int,int>> ,  greater<pair<int,int> > > pq ; 
                  vector<int> dist(n+1,INT_MAX);
                  dist[1] = 0 ; 
                    pq.push({dist[1],1});
                   while(!pq.empty()){
                       int d = pq.top().first ; 
                       int nod = pq.top().second;
                         pq.pop();
                            for(int num : adj[nod]){
                                int weight = cost[{nod,num}] ; 
                               if(dist[num] > dist[nod] + weight ){
                                    dist[num] = dist[nod] + weight ;
                                     pq.push({dist[num],num});
                               }
                            }
                   }
                      for(int i = 2 ; i <= n ; i ++ ){
                        if(dist[i] == INT_MAX)
                          dist[i] = 0 ; 
                        cout<<dist[i]<< ' ';
                      }

    return 0;
}