#include <bits/stdc++.h>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

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

struct graf {
    int nod, cost;
    bool operator < (const graf &gr) const {
        return cost > gr.cost;
    }
};

vector <graf> g[50005];
priority_queue <graf> q;
int v[50005];

void dijkstra (int start) {
    memset(v, INF, sizeof v);
    v[1] = 0;
    q.push({start, 0});
    while (!q.empty()) {
        int cost = q.top().cost;
        int nod = q.top().nod;
        q.pop();

        if (cost != v[nod]) continue;
        for (auto n : g[nod]) {
            if (v[n.nod] > cost + n.cost) v[n.nod] = cost + n.cost, q.push({n.nod, v[n.nod]});
        }
    }
}

int main()
{
    int n, m;
    fin >> n >> m;
    int a, b, c;
    for (int i = 1; i <= n; i ++) {
        fin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    dijkstra(1);
    for (int i = 2; i <= n; i ++) fout << v[i] << " ";
    return 0;
}