#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< pair<int,int> > minHeap;
vector<int> d;
vector<int> visited;
 
 
void read(){
 
    in >> N >> M;
 
    d.resize(N+1);
    d.assign(N+1, INF);
 
    visited.resize(N+1);
 
    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(c,y));
        if(x == 1){
            minHeap.push_back(make_pair(c,y));
            d[y] = c;
            visited[y] = 1;
        }
        
    }
 
    d[1] = 0;

    make_heap(minHeap.begin(),minHeap.end());
}
 
 
void Dijkstra(){

    pair<int,int> per;

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