#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int INF = 0x3f3f3f;

vector <vector <pair <int, int> > > v;
vector <int> Cost(50005, INF);

int main()
{
    int n, m, x, y, c;
    fin >> n >> m;
    v.resize(n + 1);
    for (; m; --m) {
        fin >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }
    priority_queue <pair <int, int> > q;
    q.push(make_pair(0, 1));
    while (!q.empty()) {
        int Dist = - q.top().first;
        int Node = q.top().second;

        if (Dist > Cost[Node]) {
            q.pop();
            continue;
        }
        q.pop();

        for (int i = 0; i < v[Node].size(); ++i) {
            if (Dist + v[Node][i].second < Cost[v[Node][i].first]) {
                Cost[v[Node][i].first] = Dist + v[Node][i].second;
                q.push(make_pair(-Cost[v[Node][i].first], v[Node][i].first));
            }
        }
    }

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