/*
- folosesc heap in care pun varful si distanta de la sursa la el
- fac extract(min)
- iterez prin vecinii lui
*/

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int nMax = 50001;
const int inf = 250000001;

vector < pair <int, int> > graph[nMax];
priority_queue < pair <int, int> > heap;

vector <int> minDist;
vector <bool> viz;
int n, m;

void citire() {
    int i, x, y, c;
    f >> n >> m;
    for(i = 0; i < m; i++) {
        f >> x >> y >> c;
        graph[x].push_back (make_pair(y, c));
    }
}

void dijkstra(int source) {
    int i, x, y, cost;
    minDist.resize(n + 1, inf);
    viz.resize(n + 1, false);

    minDist[source] = 0;
    heap.push(make_pair(0, source));

    while(!heap.empty()) {
        while(!heap.empty() && viz[heap.top().second]) heap.pop();

        if(heap.empty()) break;

        x = heap.top().second;
        heap.pop();
        viz[x] = true;

        for(i = 0; i < graph[x].size(); i++) {
            y = graph[x][i].first;
            cost = graph[x][i].second;

            if(minDist[y] > minDist[x] + cost) {
                minDist[y] = minDist[x] + cost;
                heap.push (make_pair(-minDist[y], y));
            }
        }
    }
}

void afis() {
    int i;
    for (i = 2; i <= n; i++) {
        if(minDist[i] == inf) g << "0 ";
            else g << minDist[i] << " ";
    }
}

int main() {
    citire();
    dijkstra(1);
    afis();

    return 0;
}