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

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){
        swap(heap[pos>>1],heap[pos]);
        pos>>=1;
    }
}

void pop(){
    int pos = 1;
    swap(heap[curr],heap[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){
            swap(heap[pos],heap[pos<<1]);
            pos = pos<<1;
        }else if(((pos<<1)|1)<=curr){
            swap(heap[pos],heap[(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)
            swap(heap[pos],heap[pos<<1]);
    }
}

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

    int n;
    cin>>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;
        cin>>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();

        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)
            cout<<0<<" ";
        else
            cout<<costs[i]<<" ";
    }
}