#include <iostream>
#include <fstream>
#include <map>
#include <climits>
#include <list>
#include <set>

using namespace std;

typedef pair<int,int> paer;

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m, i, j, a, b, c;
    in>>n>>m;

    list<paer> vecini[n+1];
    list<paer>::iterator it;
    int d[n+1];
    bool viz[n+1];
    std::fill(d, d+n+1, INT_MAX);
    std::fill(viz, viz+n+1, 0);

    for (i=0; i<m; i++) {
        in>>a>>b>>c;
        vecini[a].push_back(paer(b, c));
    }

    set<paer> dijk;

    d[1] = 0;
    dijk.insert(paer(0, 1));

    i = 0;
    while (!dijk.empty()) {
        int min = (*dijk.begin()).second;
        c = (*dijk.begin()).first;
        dijk.erase(dijk.begin());

        if (viz[min])
            continue;

        viz[min] = 1;
        for (it = vecini[min].begin(); it != vecini[min].end(); it++) {
            b = (*it).first;
            c = (*it).second;

            if (d[b] > d[min] + c) {
                d[b] = d[min] + c;
                dijk.insert(paer(d[b], b));
            }
        }
    }

    for (i=2; i<=n; i++) {
        if (d[i] == INT_MAX) {
            out<<0<<" ";
        }
        else out<<d[i]<<" ";
    }

    in.close();
    out.close();
    return 0;
}