#include<fstream>
#include<vector>
using namespace std;
int n, i, j, m, x, y, vecin, nod, cost, z, p, c;
int d[50005], viz[50005], poz[50005], h[50005];
vector< pair<int, int> > v[50005];
pair<int, int> pp;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y >> z;
        pp.first = y;
        pp.second = z;
        v[x].push_back(pp);
    }
    poz[1] = h[1] = 1;
    for(i = 2; i <= n; i++){
        d[i] = 1000000000;
        poz[i] = i;
        h[i] = i;
    }
    d[0] = 1000000000;
    for(i = 1; i <= n; i++){
        nod = h[1];
       /* for(j = 1; j <= n; j++){
            if(d[j] < d[nod] && viz[j] == 0){
                nod = j;
            }
        }*/
        viz[nod] = 1;
        for(j = 0; j < v[nod].size(); j++){
            vecin = v[nod][j].first;
            cost = v[nod][j].second;
            if(d[vecin] > d[nod] + cost && viz[vecin] == 0){
                d[vecin] = d[nod] + cost;
                c = poz[vecin];
                p = c / 2;
                while(d[h[c]] < d[h[p]] && p > 0){
                    swap(h[p], h[c]);
                    poz[h[p]] = p;
                    poz[h[c]] = c;
                    c = p;
                    p = c / 2;
                }
            }
        }
        p = 1;
        c = 2;
        while(c <= n){
            if(c + 1 <= n && d[h[c]] > d[h[c + 1]]){
                c++;
            }
            swap(h[p], h[c]);
            poz[h[p]] = p;
            poz[h[c]] = c;
            p = c;
            c = 2 * p;
        }
    }
    for(i = 2; i <= n; i++){
        if(d[i] == 1000000000){
            fout<<"0 ";
            continue;
        }
        fout<< d[i] <<" ";
    }
    return 0;
}