#include <iostream>
#include <list>
#include <fstream>
#include <vector>
#include <algorithm>
#include <bitset>

using namespace std;

struct muchiet {
    int urm;
    int cost;
};


typedef vector<muchiet> nod;

inline 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;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
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].back().urm]) {
                maux.cost=c+graf[a].back().cost;
                maux.urm=graf[a].back().urm;
                heap.push_back(maux);
                push_heap(heap.begin(),heap.end(),comp);
            }
            graf[a].pop_back();
        }
    }
}
}

int main()
{
    fin>>n>>m;
    vizitate=n;
    for(i=1;i<=m;i++) {
        fin>>a>>maux.urm>>maux.cost;
        graf[a].push_back(maux);
    }
    dijkstra();
    for(i=2;i<=n;i++) {
        fout<<minn[i]<<" ";
    }
    fout.close();

    return 0;
}