#include <bits/stdc++.h>
#define MAX 50000
#define MAX2 1000000002
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int, int>>g[MAX+5];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>h;
int cmin[MAX+5], pre[MAX+5], n, m, x, y, cost, i;
bool viz[MAX+5];
void dijkstra(int);
int main()
{
    fin>>n>>m;
    for (i=1; i<=n; i++) {
        fin>>x>>y>>cost;
        g[x].push_back({y, cost});
    }
    for (i=1; i<=n; i++) sort(g[i].begin(), g[i].end());
    dijkstra(1);
    for (i=2; i<=n; i++) {
        if (cmin[i]==MAX2) fout<<"0 ";
        else fout<<cmin[i]<<' ';
    }
    return 0;
}
void dijkstra(int x) {
    int i, mini, cnt=1, vfmin;
    for (i=1; i<=n; i++) {
        cmin[i]=MAX2;
    }
    cmin[x]=0;
    h.push({0, x});
    while (!h.empty()) {
        x=h.top().first;
        y=h.top().second;
        if (viz[y]==1) {
            h.pop();
            continue;
        }
        viz[y]=1;
        for (auto z:g[y]) {
            if (!viz[z.first] && cmin[z.first]>x+z.second) {
                cmin[z.first]=x+z.second;
                h.push({cmin[z.first], z.first});
            }
        }
        h.pop();
    }
}