#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[250001];
int i, m, n, lg, x, y, c, sol[50001], ramase;
bool viz[50001];
inline void heap_up(int poz){
    if (poz<2) return;
    if (heap[poz].f<heap[poz/2].f) {swap(heap[poz], heap[poz/2]); heap_up(poz/2);}
}
inline void heap_down(int poz){
    if (2*poz>lg) return;
    if (2*poz+1>lg) {if (heap[2*poz].f<heap[poz].f) swap(heap[poz], heap[2*poz]); return;}
    if (heap[2*poz].f<heap[2*poz+1].f) {
        if (heap[2*poz].f<heap[poz].f) {swap(heap[poz], heap[2*poz]); heap_down(2*poz);}
    } else {
        if (heap[2*poz+1].f<heap[poz].f) {swap(heap[poz], heap[2*poz+1]); heap_down(2*poz+1);}
    }
}
int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=m;++i) {scanf("%d%d%d", &x, &y, &c); a[x].push_back(make_pair(c, y));}
    lg=0; sol[1]=0; ramase=n-1; viz[1]=true;
    for (it=a[1].begin();it!=a[1].end();it++) {
        heap[++lg]=*it;
        heap_up(lg);
    }
    do {
        x=heap[1].f; y=heap[1].s;
        if (!viz[y]) {
            viz[y]=true;
            sol[heap[1].s]=x;
            for (it=a[y].begin();it!=a[y].end();++it)
            if (!viz[(*it).s]) {
                heap[++lg]=make_pair(heap[1].f+(*it).f, (*it).s);
                heap_up(lg);
            }
        }
        swap(heap[1], heap[lg]); heap[lg]=make_pair(0,0); lg--;
        heap_down(1);
    } while (lg>0);
    for (i=2;i<=n;i++) printf("%d ", sol[i]); printf("\n");
    return 0;
}