#include <fstream>
#include <vector>
#include <queue>

#define NMAX 50010
#define INF 1<<30

using namespace std;

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

struct Nod {
    int y, cost;
    Nod() {
        y = 0;
        cost = 0;
    }
    Nod(int y, int cost) {
        this->y = y;
        this->cost = cost;
    }
    inline bool operator<(const Nod& x) const {
        return x.cost < cost;
    }
};
priority_queue <Nod> q;
vector <Nod> v[NMAX];
int x, y , cost, n, m, d[NMAX], nod, viz[NMAX];
Nod t = Nod();

void dijkstra() {
    q.push(Nod(1, 0));
    while(!q.empty()) {
        nod = q.top().y;
        q.pop();
        if(viz[nod] == 0) {
            viz[nod] = 1;
            for (int i = 0; i < v[nod].size(); ++i) {
                if (d[nod] + v[nod][i].cost < d[v[nod][i].y]) {
                    d[v[nod][i].y] = d[nod] + v[nod][i].cost;
                    q.push(Nod(v[nod][i].y, d[v[nod][i].y]));
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 0; i < n; ++i) {
        fin >> x >> y >> cost;
        v[x].push_back(Nod(y, cost));
    }
    for (int i = 2; i <= n; ++i) {
        d[i] = INF;
    }
    dijkstra();
    for (int i = 2; i <= n; ++i)
        fout << d[i] << " ";
    return 0;
}