#include <vector>
#include <fstream>
#include <queue>
using namespace std;
const int Dim= 100005;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector<pair<int,int>>G[Dim];
int D[Dim],n,m;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;

int main(){
    
    cin >> n >> m;
    for(int i = 1,x,y,c; i <= m; ++i){
        cin >> x>>y>>c;
        G[x].push_back({y,c});
        
    }
   
    for(int i = 1 ;i <= n; ++i)
        D[i] = 0x3f3f3f3f;
    D[1] = 0;
    q.push({0,1});
    while(!q.empty()) {
        
        int nod = q.top().second;
        int cost = q.top().first;
        q.pop();
        if(cost > D[nod])
            continue;
        for(auto y: G[nod]) {
            if(D[y.first] >cost+y.second )
                {D[y.first] =cost+y.second;
                q.push({D[y.first],y.first});
                }
            
        }
        }
            
            
    
    for(int i = 2; i <= n; ++i)
    if(D[i] == 0x3f3f3f3f)
        cout << "0 ";
    else cout << D[i] << " ";
 }