#include <bits/stdc++.h>

using namespace std;

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

vector <pair <int, int> > g[50005];
int v[50005];
queue <int> q;

void bfs (int start)
{
    q.push(1);
    while (!q.empty()) {
        int nod = q.front(), n = g[nod].size();
        for (int i = 0; i < n; i ++) {
            if (g[nod][i].first != 1 && v[g[nod][i].first] == 0) {
                q.push(g[nod][i].first);
                v[g[nod][i].first] = v[nod] + g[nod][i].second;
            }
            else if (g[nod][i].first != 1 && g[nod][i].second + v[nod] < v[g[nod][i].first]) {
                v[g[nod][i].first] = v[nod] + g[nod][i].second;
                q.push(g[nod][i].first);
            }
        }
        q.pop();
    }
}

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});
    }
    bfs(1);
    for (int i = 2; i <= n; i ++) fout << v[i] << " ";
    return 0;
}