#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int inf = 0x3f3f3f3f;
int n, m, x, y, c, k[50001], p[50001];
struct muchie{
    int dest, val;
    muchie(int a, int b){
        dest = a; val = b;
    }
};
vector<muchie> graf[50001];
vector<int> h;

void downheap(int poz){
    int minim = poz;
    int st = poz*2+1;
    int dr = poz*2+2;
    if(st < h.size() && k[h[st]] < k[h[minim]]) minim = st;
    if(dr < h.size() && k[h[dr]] < k[h[minim]]) minim = dr;
    if(minim != poz){
        swap(h[poz], h[minim]);
        swap(p[h[poz]], p[h[minim]]);
        downheap(minim);
    }
}

void upheap(int poz){
    int root = (poz-1)/2;
    if(root >= 0 && k[h[root]] > k[h[poz]]){
        swap(h[poz], h[root]);
        swap(p[h[poz]], p[h[root]]);
        upheap(root);
    }
}

void popheap(int poz){
    swap(h[poz], h[h.size()-1]);
    swap(p[h[poz]], p[h[h.size()-1]]);
    h.pop_back();
    downheap(poz);
}

int main(){
    fin>>n>>m;
    for(int i=1; i<=n; i++){
        h.push_back(i);
        p[i] = i-1;
        if(i>1) k[i] = inf;
    }
    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        graf[x].push_back(muchie(y, c));
    }
    while(!h.empty()){
        int nod = h[0];
        for(int i=0; i<graf[nod].size(); i++){
            int nk = graf[nod][i].val + k[nod], dest = graf[nod][i].dest;
            if(nk < k[dest]){
                k[dest] = nk;
                upheap(p[dest]);
            }
        }
        popheap(0);
    }
    for(int i=2; i<=n; i++)
        fout<<(k[i]==inf?0:k[i])<<" ";
    fout<<"\n";
}