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

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

#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;
    }
};

void dijkstra(int Source, int N, vector<Nod > Graf[]){
    
    vector<int> distante;
    for(int i = 0; i <= N; i++){
        distante.push_back(INF);
    }
        
    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();
        if(distante[aux.varf] != aux.cost)
            continue;
        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]));
            }
        }
        
    } 
    for(int i = 2; i <= N; i++){
        if(distante[i] == INF)
            out << "0 ";
        else
           out << distante[i] <<" ";
    }
    out <<"\n";            
    
    
}

int main() {
   
    int  N, M, x, y , c; 
    vector< Nod > Graf [50001];
    in >> N >> M;
    for(int i = 0; i < M; i++){
        in >> x >> y >> c;
        Graf[x].push_back(Nod(y, c) );
    }
    dijkstra(1, N, Graf);
     
    return 0;
}