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

#define c first
#define v second

using namespace std;

const int oo = 0x3f3f3f3f;

vector<vector<pair<int, int>>> G;
int V;
vector<int> Distances;

void Dijkstra(int source, vector<int> &distance) {
    distance = vector<int>(V, oo);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push(make_pair(0, source));
    while (!heap.empty()) {
        int x = heap.top().v, cost = heap.top().c;
        heap.pop();
        if (distance[x] != oo)
            continue;
        distance[x] = cost;
        for (auto &y: G[x])
            if (distance[y.v] == oo)
                heap.push(make_pair(cost + y.c, y.v));
    }
}

void Read() {
    ifstream in("dijkstra.in");
    int E; in >> V >> E;
    G = vector<vector<pair<int, int>>>(V);
    for (; E > 0; --E) {
        int x, y, cost; in >> x >> y >> cost;
        --x; --y;
        G[x].push_back(make_pair(cost, y));
    }
    in.close();
}

void Print() {
    ofstream out("dijkstra.out");
    for (int x = 1; x < V; ++x) {
        if (Distances[x] == oo)
            Distances[x] = 0;
        out << Distances[x] << " ";
    }
    out << "\n";
    out.close();
}

int main() {
    Read();
    Dijkstra(0, Distances);
    Print();
    return 0;
}