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

int curr=0,m;
struct strc{
    int val,nod;
};
vector<strc> heap;

void swaps(int x,int y){
    strc 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].val<heap[pos].val and pos!=1){
        swaps(pos>>1,pos);
        pos>>=1;
    }
}

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

    while((pos*2<=curr and heap[pos*2].val>heap[pos].val)or(pos*2+1<=curr and heap[pos*2+1].val>heap[pos].val)){
        int id=pos*2;
        if(pos*2+1 <= curr and heap[pos*2+1].val>heap[pos*2].val)
            id++;
        swaps(pos,id);
        id*=2;
    }
}

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].nod;
        int currcost = heap[1].val;
        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]);
    }
}