#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <fstream>
using namespace std;

#define INF 1234567
struct Nod{
    int varf, cost;
    Nod(int varf, int cost)
    :varf(varf)
    ,cost(cost)
    {}
    
};

class mycomparison{
    public:
    bool operator() (const Nod & n1, const Nod & n2) const{
        return n1.cost < n2.cost;
    }
};


vector<int>  dijkstra(int Source, int N, vector<Nod > Graf[]){
    
    vector<int> distante;
    vector<bool> vizitat;
    for(int i = 0; i <= N; i++){
        distante.push_back(INF);
        vizitat.push_back(false);
    }
        
    distante[Source] = 0;
    priority_queue<Nod, vector<Nod> , mycomparison> Q;
    Q.push(Nod(Source, distante[Source]));
    while( ! Q.empty()){
        Nod aux = Q.top();
        Q.pop();
        vizitat[aux.varf] = true;
        for(size_t i = 0; i < Graf[aux.varf].size(); i++){
           if(distante[aux.varf] + Graf[aux.varf][i].cost < distante[Graf[aux.varf][i].varf])
           {
                 distante[Graf[aux.varf][i].varf] = distante[aux.varf] + Graf[aux.varf][i].cost;
                 Q.push(Nod(Graf[aux.varf][i].varf, distante[Graf[aux.varf][i].varf]));
           }
       }
        
    } 
    return distante;            
    
    
}

int main() {
   
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int  N, M, x, y , c, S;
    vector< Nod > Graf [50001];
    vector<int > distante;
    in >> N >> M;
    for(int i = 0; i < M; i++){
        in >> x >> y >> c;
        Graf[x].push_back(Nod(y, c) );
    }
    distante = dijkstra(1, N, Graf);
    for(int i = 2; i <= N; i++){
        if(distante[i] == INF)
            out << "0 ";
        else
           out << distante[i] <<" ";
    }
    out <<"\n"; 
    return 0;
}