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

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<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<utility>
#include<climits>
using namespace std ; 
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int main()
{

    int n , m ; 
    
    cin>>n>>m;
     int x , y , c ; 
        vector<vector<pair<int,int>>>adj(n+1);
          for(int i = 1 ; i <= m ; i ++ ){
                cin>>x>>y>>c;
                  adj[x].push_back({y,c});
          }
            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 len = pq.top().first ; 
                int node = pq.top().second ; 
             pq.pop();
                if(len > dist[node] )
                  continue ; 
         for(auto &v : adj[node] ){
               int nei = v.first ; 
               int weight = v.second ;
                 if(dist[nei] > dist[node] + weight ){
                       dist[nei] = dist[node] + weight ; 
                       pq.push({dist[nei],nei});
                 }
         }
        }
          for(int i = 2 ; i <= n ;i ++ ){
                 if(dist[i] == INT_MAX )
                    dist[i] = - 1; 
                cout<<dist[i]<< ' ';
          }




    return 0;
}