#include <iostream>
#include <fstream>
#include <map>
#include <deque>
#include <climits>

using namespace std;

typedef pair<int,int> paer;

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

    int noduri[n+1];
    bool viz[n+1];
    std::fill(noduri, noduri+n+1, INT_MAX);
    std::fill(viz, viz+n+1, 0);
    map<int, deque<paer>> vecini;

    noduri[1] = 0;

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

    deque<int> dijk;
    dijk.push_back(1);
    i = 0;

    while (i < n) {
        a = dijk[i];
        viz[a] = 1;

        for (j = 0; j<vecini[a].size(); j++) {
            b = vecini[a][j].first;
            c = vecini[a][j].second;

            if (noduri[a] + c < noduri[b]) {
                noduri[b] = noduri[a] + c;
            }

            if (!viz[b]) {
                dijk.push_back(b);
            }
        }
        i++;
    }

    for (i=2; i<=n; i++) {
        out<<noduri[i]<<" ";
    }

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