#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;

}