#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, a, b, c;
    in>>n>>m;

    map<int, deque<paer>> vecini;
    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));
    }

    d[1] = 0;

    i = 0;
    while (i < n) {
        int min = 0;
        for (j=1; j<=n; j++) if (!viz[j] && d[j] < d[min]) min = j;

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

            if (d[b] > d[min] + c) {
                d[b] = d[min] + c;
            }
        }

        i++;
    }

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

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