#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
#include <limits>
using namespace std;

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

    map<int, map<int, int> > g;

    int n, m, i, minim, alt, c = 1, x, y;

    in >> n >> m;

    const int infinite = numeric_limits<int>::max();
    vector<int> cost(n + 1, infinite);
    cost[1] = 0;
    vector<bool> viz(n + 1, false);
    map<int, int>::iterator it, eit;
    pair<int, int> v;

    for (i = 0; i < m; i++) {
        in >> x >> y;
        in >> g[x][y];
        if (x == 1) {
            cost[y] = g[x][y];
        }
    }


    while (true) {
        viz[c] = true;

        it = g[c].begin(); eit = g[c].end();
        for (; it != eit; ++it) {
            v = *it;
            alt = cost[c] + v.second;
            if (!viz[v.first] && alt < cost[v.first]) {
                cost[v.first] = alt;
            }
        }

        minim = infinite;
        for (i = 1; i <= n; i++) {
            if (!viz[i] && cost[i] < minim) {
                minim = cost[i];
                c = i;
            }
        }
        if (minim == infinite) {
            break;
        }
    }

    for (i = 2; i <= n; i++) {
        out << cost[i] << ' ';
    }

    in.close();
    out.close();

    return 0;
}