#include<cstdio>
#include<vector>
#include<algorithm>
#define f first
#define s second
using namespace std;
vector<pair<int,int> > a[50001];
vector<pair<int,int> >::iterator it;
pair<int,int> heap[150001];
int i, n, m, x, y, l, lg_heap=0, rms, sol[50001];
bool viz[50001];
inline void heap_up(int poz){
    while (poz>1) {
        if (heap[poz/2].f>heap[poz].f) {swap(heap[poz], heap[poz/2]); poz/=2;}
        else poz=-1;
    }
}
inline void heap_down(int poz){
    while (2*poz<=lg_heap){
        if (2*poz+1>lg_heap) {
            if (heap[2*poz].f<heap[poz].f) swap(heap[poz], heap[2*poz]);
            poz=lg_heap+1;
        }
        if (heap[2*poz].f<=heap[2*poz+1].f) {
            if (heap[2*poz].f<heap[poz].f) {swap(heap[poz], heap[2*poz]); poz*=2;}
                else poz=lg_heap+1;
        } else {
            if (heap[2*poz+1].f<heap[poz].f) {swap(heap[poz], heap[2*poz+1]); poz=2*poz+1;}
                else poz=lg_heap+1;
        }
    }
}
int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=n;i++) {
        scanf("%d%d%d", &x, &y, &l);
        a[x].push_back(make_pair(l, y));
    }
    for (it=a[1].begin();it!=a[1].end();it++) {
        heap[++lg_heap]=*it;
        heap_up(lg_heap);
    }
    viz[1]=true; rms=n-1; /*sol[1]=0*/
    do {
        x=heap[1].f; y=heap[1].s;
        if (!viz[y]) {
            rms--;
            viz[y]=true;
            sol[heap[1].s]=x;
            for (it=a[y].begin();it!=a[y].end();it++) if (!viz[(*it).s]) {
                heap[++lg_heap]=make_pair((*it).f+heap[1].f, (*it).s); ///pair<lungime, destinatie>
                heap_up(lg_heap);
            }
        }
        swap(heap[1], heap[lg_heap]);
        heap[lg_heap]=make_pair(0,0);
        lg_heap--;
        heap_down(1);
    } while ((rms>0)||(lg_heap>0));
    for (i=2;i<=n;i++) printf("%d ", sol[i]); printf("\n");
    return 0;
}