#include <bits/stdc++.h>
using namespace std;

int curr=0,m;
vector<pair<int,int>> heap;

void swaps(int x,int y){
    pair<int,int> org = heap[x];
    heap[x] = heap[y];
    heap[y] = org;
}

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

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

    while(heap[pos>>1].first<heap[pos].first and pos!=1){
        swaps(pos>>1,pos);
        pos>>=1;
    }
}

void pop(){
    int pos = 1;
    swaps(curr,1);
    curr--;

    while(heap[pos].first < max(heap[pos<<1].first,heap[(pos<<1)|1].first) and (pos<<1)<=curr){
        if(heap[pos].first < heap[pos<<1].first){
            swaps(pos,pos<<1);
            pos = pos<<1;
        }else if(((pos<<1)|1)<=curr){
            swaps(pos,(pos<<1)|1);
            pos = (pos<<1)|1;
        }else
        break;
        
        if((pos<<1)>curr or ((pos<<1)|1)>curr)
        break;
    }
    if((pos<<1)<=curr){
        if(heap[pos].first < heap[pos<<1].first)
            swaps(pos,pos<<1);
    }
}

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n;
    scanf("%d%d",&n,&m);

    vector<vector<pair<int,int>>> v(n+1);
    vector<int> costs(n+1,INT_MAX);
    heap.resize(300000);

    for(int i=1;i<=m;i++){
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);

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

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

    while(curr){
        int nod = heap[1].second;
        int currcost = heap[1].first;
        pop();
        if(costs[nod] == currcost){
            for(int i = 0;i<v[nod].size();i++){
                int newnod = v[nod][i].first;
                int 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]==INT_MAX)
            printf("0 ");
        else
            printf("%d ", costs[i]);
    }
}