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

using namespace std;

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

const int NMax = 50005;
const int INF = 0x3f3f3f3f;

int n, p;
int dis[NMax];
bool vizitat[NMax];

vector<pair<int, int> > graf[NMax];

struct cmp {
    bool operator()(int x, int y) {
        return graf[x] > graf[y];
    }
};

priority_queue<int, vector<int>, cmp> coada;

void citeste() {
    fin >> n >> p;
    int x, y, c;
    while (fin >> x >> y >> c) {
        graf[x].push_back({y, c});
    }
}

void afisare() {
    for (int i = 2; i <= n; i++) {
        if (dis[i] != INF)
            fout << dis[i] << ' ';
        else
            fout << -1 << ' ';
    }
}

void Dijkstra() {
    for (int i = 1; i <= n; i++)
        dis[i] = INF;

    dis[1] = 0;
    coada.push(1);

    while (!coada.empty()) {
        int nodCurent = coada.top();
        coada.pop();

        for (const auto& i: graf[nodCurent]) {
            int vecin = i.first;
            int cost = i.second;
            if (dis[nodCurent] + cost < dis[vecin]) {
                dis[vecin] = dis[nodCurent] + cost;
                coada.push(vecin);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    citeste();
    Dijkstra();
    afisare();
    return 0;
}