#include <iostream>
#include <vector>
#include <set>
#include <fstream>
#define dmax 50005
#define INF 99999999

using namespace std;

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

int n, m, x, y, w;
vector<pair<int, int> > graf[dmax];
multiset<pair<int ,int> > ms;
pair<int, int> pVerif;
int dist[dmax];
bool viz[dmax];

int cur_x, cur_c;
int newV, cost;

int main() {
    int i, j;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> w;
        graf[x].push_back({y, w});
    }

    for (i = 2; i <= n; i++) {
        dist[i] = INF;
    }
    ms.insert({0, 1});
    while (!ms.empty()) {
        pVerif = *ms.begin();
        ms.erase(ms.begin());
        cur_x = pVerif.second;
        cur_c = pVerif.first;
        if (viz[cur_x]) continue;
        viz[cur_x] = true;
        for (i = 0; i < graf[cur_x].size(); i++) {
            newV = graf[cur_x][i].first;
            cost = graf[cur_x][i].second;
            if (dist[newV] > dist[cur_x] + cost) {
                dist[newV] = dist[cur_x] + cost;
                ms.insert({dist[newV], newV});
            }
        }
    }
    for (i = 2; i <= n; i++) {
        if (dist[i] == INF) fout << "0 ";
        else fout << dist[i] << ' ';
    }
    return 0;
}