#include <fstream>
#include <vector>
#define DIM 50010
#define INF 1000000000

using namespace std;
vector<pair<int, int> > L[DIM];
int v[DIM], D[DIM];
int n, m, i, nod, vecin, cost, x, y, c, minim;
int main () {
    ifstream fin ("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;

    for (i=1;i<=m;i++){
        fin>>x>>y>>c;
        L[x].push_back( make_pair(y, c) );
    }

    D[1] = 0;
    for (i=2;i<=n;i++)
        D[i] = INF;

    for (;;) {
        minim = INF;
        for (i=1;i<=n;i++)
            if (v[i] == 0 && D[i] < minim) {
                minim = D[i];
                nod = i;
            }
        /// nod va fi mininul din D dintre nodurile nealese
        if (minim == INF)
            break;

        v[nod] = 1;
        for (i=0;i<L[nod].size();i++) {
            vecin = L[nod][i].first;
            cost = L[nod][i].second;

            if (D[vecin] > D[nod] + cost)
                D[vecin] = D[nod] + cost;
        }

    }
    for (i=2;i<=n;i++)
        if (D[i] == INF)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";
    return 0;
}