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

int main () {
    int n, m, i, a, b, c;
    const int inf = numeric_limits<int>::max();
    queue<int> q;
    vector<pair<int, int> >::iterator it, eit;

    ifstream in("dijkstra.in");
    in >> n >> m;
    vector<pair<int, int> > g[n + 1];
    vector<int> dist(n + 1, inf);
    vector<bool> viz(n + 1, false);
    dist[1] = 0;
    viz[1] = true;
    for (i = 0; i < m; i++) {
        in >> a >> b >> c;
        g[a].push_back(make_pair(b, c));
    }
    in.close();

    q.push(1);
    while (!q.empty()) {
        i = q.front();
        q.pop();
        viz[i] = false;
        for (it = g[i].begin(), eit = g[i].end(); it != eit; ++it) {
            if (dist[i] + it->second < dist[it->first]) {
                dist[it->first] = dist[i] + it->second;
                if (!viz[it->first]) {
                    viz[it->first] = true;
                    q.push(it->first);
                }
            }
        }
    }

    ofstream out("dijkstra.out");
    for (i = 2; i <= n; i++) {
        out << (dist[i] == inf ? 0 : dist[i]) << ' ';
    }
    out.close();

    return 0;
}