#include <bits/stdc++.h>
#define oo 2147483647

using namespace std;

vector< pair<int, int> > G[50005];
int d[50005];
bool viz[50005];

//pentru heap
int H[100005];
int heap = 1;

void down(int i) {
    int son;
    int rs, ls;
    do {
        son = 0;
        ls = i * 2;
        rs = i * 2 + 1;
        if(rs <= heap) {
            if(d[ H[ls] ] > d[ H[rs] ])
                son = rs;
            else son = ls;
        }
        else if(ls <= heap) {
            son = ls;
        }

        if(d[ H[son] ] < d[ H[i] ]) {
            int aux = H[son];
            H[son] = H[i];
            H[i] = aux;
            i = son;
        }
        else son = 0;
    }
    while(son != 0);
}

void up(int i) {
    while(i > 1) {
        if(d[ H[ i / 2 ] ] > d[ H[i] ]) {
            int aux = H[i / 2];
            H[i / 2] = H[i];
            H[i] = aux;
            i /= 2;
        }
        else return;
    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int n, m, x, y, cost;
    f >> n >> m;
    for(int i = 1; i <= m; i ++) {
        f >> x >> y >> cost;
        G[x].push_back({y, cost});
    }

    for(int i = 2; i <= n; i ++) d[i] = oo;

    H[1] = 1;

    while(heap > 0) {
        int nod = H[1];
        H[1] = H[heap];
        heap --;
        down(1);
        viz[nod] = true;

        for(auto j: G[nod]) {
            if(d[j.first] > d[nod] + j.second) {
                d[j.first] = d[nod] + j.second;
                if(!viz[j.first]) {
                    heap ++;
                    H[heap] = j.first;
                    up(heap);
                }
            }
        }
    }

    for(int i = 2; i <= n; i ++) {
        if(d[i] == oo) d[i] = 0;
        g << d[i] << " ";
    }
    g << "\n";
    return 0;
}