#include <fstream>
#include <vector>
#define oo 1<<30

using namespace std;

vector< pair<int, int> > L[50005];
int d[50005], t[50005], poz[50005];
bool viz[50005];



int H[100105];
int l; //length of heap

void cobor(int x) {
    int son;

    do {
        son = 0;
        int ls = x * 2;
        int rs = ls + 1;
        if(rs <= l) {
            if(d[ H[ls] ] > d[ H[rs] ]) {
                son = rs;
            }
            else son = ls;
        }
        else if(ls <= l) son = ls;

        if(d[ H[son] ] >= d[ H[x] ]) son = 0;
        else {
            int aux = H[x];
            H[x] = H[son];
            H[son] = aux;

            poz[ H[x] ] = son;
            poz[ H[son] ] = x;

            x = son;
        }
    }
    while(son != 0);
}

void urc(int x) {
    int tata;
    while(x > 1) {
        tata = x / 2;
        if(d[ H[x] ] < d[ H[tata] ]) {

            poz[ H[x] ] = tata;
            poz[ H[tata] ] = x;

            int aux = H[tata];
            H[tata] = H[x];
            H[x] = aux;
            x = tata;
        }
        else x = 1;
    }
}



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

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

    for(int i = 2; i <= n; i ++)
        d[i] = oo, poz[i] = -1;

    poz[1] = 1;
    l = 1;
    H[l] = 1;

    while(l) {
        int mn = H[1];
        int aux = H[1];
        H[1] = H[l];
        H[l] = aux;
        poz[H[1]] = 1;
        l --;

        cobor(1);

        for(int i = 0; i < L[mn].size(); i ++) {
            int nod = L[mn][i].first;
            int cost = L[mn][i].second;
            if(d[nod] > d[mn] + cost) {
                d[nod] = d[mn] + cost;
                t[nod] = mn;
                if(poz[nod] != -1)
                    urc(poz[nod]);
                else {
                    l ++;
                    H[l] = nod;
                    poz[nod] = l;
                    urc(l);
                }
            }
        }

    }

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