#include <iostream>
#include <list>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

struct muchiet {
    int urm;
    int cost;
};


typedef list<muchiet> nod;

bool comp(muchiet a, muchiet b) {
    return (a.cost>b.cost);
}


int n,m,i,j,a,b,c,vizitate;
nod graf[50002];
muchiet maux;
FILE *fin=fopen("dijkstra.in","r"),*fout=fopen("dijkstra.out","w");
vector<muchiet> heap;
bitset<50002> vizitat;
int minn[50002];

void dijkstra()
{
maux.urm=1;
maux.cost=0;
heap.push_back(maux);
make_heap(heap.begin(),heap.end(),comp);

while (vizitate&&(!heap.empty())) {
    c=heap.front().cost;
    a=heap.front().urm;
    pop_heap(heap.begin(),heap.end(),comp);
    heap.pop_back();
    if (!vizitat[a]) {
        vizitat[a]=1;
        vizitate--;
        minn[a]=c;

        while(!graf[a].empty()) {
            if (!vizitat[graf[a].front().urm]) {
                maux.cost=c+graf[a].front().cost;
                maux.urm=graf[a].front().urm;
                heap.push_back(maux);
                push_heap(heap.begin(),heap.end(),comp);
            }
            graf[a].pop_front();
        }
    }
}
}

int main()
{
    fscanf(fin,"%d %d\n",&n,&m);
    vizitate=n;
    for(i=1;i<=m;i++) {
        fscanf(fin,"%d %d %d\n",&a,&(maux.urm),&(maux.cost));
        graf[a].push_front(maux);
    }
    dijkstra();
    for(i=2;i<=n;i++) {
        fprintf(fout,"%d ",minn[i]);
    }
    fclose(fout);

    return 0;
}