#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define NMAX 50010

using namespace std;

const int INF = 0x3f3f3f3f;
vector<pair<int, int>> edges[NMAX];
set<pair<int, int>> heap;
int n, m, distances[NMAX];

void readData() {
    ifstream fin("dijkstra.in");
    int x, y, cost;
    fin >> n >> m;
    for (int i=0; i<m; i++) {
        fin >> x >> y >> cost;
        edges[x].push_back(make_pair(y, cost));
    }
}

void initializeArray() {
    for (int i=1; i<=n; i++)
        distances[i] = INF;
}

void dijkstra() {
    distances[1] = 0;
    heap.insert(make_pair(0, 1));
    while(!heap.empty()) {
        pair<int, int> currentEdge;
        currentEdge.second = heap.begin()->first;
        currentEdge.first = heap.begin()->second;
        heap.erase(heap.begin());
        for (auto it: edges[currentEdge.first]) {
            if (distances[it.first] > distances[currentEdge.first] + it.second) {
                if (distances[it.first] != INF) {
                    heap.erase(heap.find(make_pair(distances[it.first], it.first)));
                }
                distances[it.first] = distances[currentEdge.first] + it.second;
                heap.insert(make_pair(distances[it.first], it.first));
            }
        }
    }
}

void printSolution() {
    ofstream fout("dijkstra.out");
    for (int i=2; i<=n; i++) {
        if (distances[i] == INF)
            distances[i] = 0;
        fout << distances[i] << " ";
    }
}

int main() {
    readData();
    initializeArray();
    dijkstra();
    printSolution();
    return 0;
}