#include <bits/stdc++.h>
using namespace std;
int curr=0,m;
vector<pair<long long,int>> heap;

void pushback(long long val,int nod){
    curr++;

    int pos = curr;
    heap[curr] = {val,nod};

    while(heap[pos/2].first<heap[pos].first and pos/2>=1){
        swap(heap[pos/2],heap[pos]);
        pos/=2;
    }
}

void pop(){
    int pos = 1;
    swap(heap[curr],heap[1]);
    curr--;

    while(heap[pos].first < max(heap[pos*2].first,heap[pos*2+1].first) and pos*2<=curr){
        if(heap[pos].first < heap[pos*2].first){
            swap(heap[pos],heap[pos*2]);
            pos = pos*2;
        }else if(pos*2+1<=curr){
            swap(heap[pos],heap[pos*2+1]);
            pos = pos*2+1;
        }else
        break;
        
        if(pos*2>m or pos*2+1>m)
        break;
    }
    if(heap[pos].first < heap[pos*2].first)
        swap(heap[pos],heap[pos*2]);
}

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int n;
    cin>>n>>m;

    vector<vector<pair<int,int>>> v(n+1);
    vector<long long> costs(n+1,LONG_MAX);
    heap.resize(m+1);

    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>c;

        v[x].push_back({y,c});
    }

    costs[1] = 0;
    pushback(0,1);

    while(curr){
        int nod = heap[1].second;
        long long currcost = heap[1].first;
        pop();

        for(int i = 0;i<v[nod].size();i++){
            int newnod = v[nod][i].first;
            long long newcost = v[nod][i].second + currcost;
            
            if(costs[newnod]>newcost){
                costs[newnod] = newcost;
                pushback(newcost,newnod);
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(costs[i]==LONG_MAX)
            cout<<0<<" ";
        else
            cout<<costs[i]<<" ";
    }
}