#include <fstream>
#include <vector>
#include <utility>
#include <set>

using namespace std;

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

const int DIM = 50010;
const long long INF = 6000000000;

int n, m, x, y, c;
long long dist[DIM];
vector<pair<int, int>> l[DIM];
set<pair<long long, int>> s;

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

    for (int i = 1; i <= n; i++)
        dist[i] = INF;

    dist[1] = 0;
    s.insert(make_pair(0, 1));
    while (!s.empty()) {
        int node = s.begin()->second;
        s.erase(s.begin());

        for (int i = 0; i < l[node].size(); i++) {
            int adjNode = l[node][i].first;
            int cost = l[node][i].second;
            if (dist[adjNode] > dist[node] + cost) {
                s.erase(make_pair(dist[adjNode], adjNode));
                dist[adjNode] = dist[node] + cost;
                s.insert(make_pair(dist[adjNode], adjNode));
            }
        }
    }

    for (int i = 2; i <= n; i++)
        fout << dist[i] << ' ';

    return 0;
}