#include <bits/stdc++.h>
#define Nmax 50005
#define pi pair<int, int>
using namespace std;

     ifstream f("dijkstra.in");
     ofstream g("dijkstra.out");

vector <pi> v[Nmax];
priority_queue <pi, vector<pi>, greater<pi> > q;
int N, M;
int ans[Nmax];
bool vis[Nmax];
int main()
{
    f >> N >> M;
    for (int i = 1; i <= N; ++i) {
        int x, y, d;
        f >> x >> y >> d;
        v[x].push_back(make_pair(d, y));
    }

    q.push(make_pair(0, 1));
    vis[1] = 1;

    while (!q.empty()) {
        int dist = q.top().first;
        int node = q.top().second;
        ans[node] = dist;
        q.pop();

        for (auto it: v[node])
          if (!vis[it.second]) {
            int dist2 = dist + it.first;
            int node2 = it.second;
            vis[node2] = 1;
            q.push(make_pair(dist2, node2));
        }
    }

    for (int i = 2; i <= N; ++i)
        g << ans[i] << ' ';

    return 0;
}