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

void pushback(long long val,int nod){
    curr++;
    heap[curr]= {val,nod};
    int pos = curr;
    while(heap[pos/2].first<heap[pos].first){
        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)){
        if(heap[pos].first < heap[pos*2].first){
            swap(heap[pos],heap[pos*2]);
            pos = pos*2;
        }else{
            swap(heap[pos],heap[pos*2+1]);
            pos = pos*2+1;
        }
    }
}

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

    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>> v(n+1);
    for(int i=1;i<=n;i++){
        int x,y,c;
        cin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    heap.resize(n+1);
    vector<long long> costs(n+1,LONG_MAX);
    costs[1] = 0;
    pushback(0,1);

    while(curr){
        int nod = heap[curr].second;
        int currcost = heap[curr].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++)
        cout<<costs[i]<<" ";
}