#include <stdio.h>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>
 
#define INF 1<<30
 
using namespace std;
 
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
 
 
int N, M;
vector< vector< pair<int,int> > > neigh;
vector<int> minHeap;
vector<int> d;
vector<bool> in_heap;
 
 
 
struct comparator{
    bool operator()(int x, int y){
        return d[x] > d[y];
         
    }
};
 
void read(){
 
    in >> N >> M;
 
    d.resize(N+1);
    d.assign(N+1, INF);
 
    in_heap.resize(N+1);
    in_heap.assign(N+1,false);
 
    for(int i = 0; i <= N; ++i){
        vector< pair<int,int> > v;
        neigh.push_back(v);
    }
 
    int x, y, c;
 
    for(int i = 0; i < M; ++i){
        in >> x >> y >> c;
        neigh[x].push_back(make_pair(y,c));
        
    }
 
}
 
 
void Dijkstra(){

    for(unsigned int i = 0; i < neigh[1].size(); ++i){
        minHeap.push_back(neigh[1][i].first);
        d[neigh[1][i].first] = neigh[1][i].second;
        in_heap[neigh[1][i].first] = true;
    }
 
    make_heap(minHeap.begin(), minHeap.end(), comparator());
 
    while(!minHeap.empty()){
 
        int u = minHeap.front();
 
        pop_heap(minHeap.begin(), minHeap.end(), comparator());
        minHeap.pop_back();
 
        for(int i = 0; i < neigh[u].size(); ++i){
            int v = neigh[u][i].first;
            int dist = d[u] + neigh[u][i].second;
 
            if(d[v] > dist){
                d[v] = dist;
                if(in_heap[v]){
                    push_heap(minHeap.begin(), minHeap.end(), comparator());
                }
                else{
                    minHeap.push_back(v);
                    push_heap(minHeap.begin(), minHeap.end(), comparator());
                    in_heap[v] = true;
                }
            }
        }
    }
}
 
 
int main(){
 
    read();
    Dijkstra();
 
    for(int i = 2; i <=N; ++i){
        if(d[i] == INF)
            out << 0 << " ";
        else out << d[i] << " ";
    }
 
}