#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int INF = 1e9 + 5;
int n, m , dist[50100];
vector<pair<int, int>> edges[250100];
set<pair<int, int>> s;

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

void dijkstra() {
    s.insert(make_pair(1, 0)); // nod + dist pana la nod
    while(!s.empty()) {
        int node = s.begin()->first;
        s.erase(s.begin());
        for (int i = 0; i < edges[node].size(); ++i) {
            int vecin = edges[node][i].first;
            int cost = edges[node][i].second;
            if (dist[vecin] > dist[node] + cost) {
                if (dist[vecin] != INF) {
                    s.erase(s.find(make_pair(vecin, dist[vecin])));
                }
                dist[vecin] = dist[node] + cost;
                s.insert(make_pair(vecin, dist[vecin]));
            }
        }
    }
}

int main() {
    fin.tie(0);
    ios::sync_with_stdio(0);
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        edges[x].push_back(make_pair(y, z));
    }
    for (int i = 2; i <= n; ++i) {
        dist[i] = INF;
    }
    dijkstra();
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF) {
            dist[i] = 0;
        }
        fout << dist[i] << " ";
    }
    return 0;
}