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

int n, m;
vector<pair<int, int>> edges[250010];
int dist[25010];
set<pair<int, int>> s;

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

void djkstra() {
    while(!s.empty()) {
        int node = s.begin()->second;
        s.erase(s.begin());
        for(int i = 0; i < edges[node].size(); ++i) {
            int to = edges[node][i].first;
            int cost = edges[node][i].second;
            if (dist[to] > dist[node] + cost) {
                if (dist[to] != 1e9) {
                    s.erase(s.find(make_pair(dist[to], to)));
                }
                dist[to] = dist[node] + cost;
                s.insert(make_pair(dist[to], to));
            }
        }
    }
}

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 = 1; i <= n; ++i) {
        for (int j = 0; j < edges[i].size(); ++j) {
            fout << i << " " << edges[i][j].first << " " << edges[i][j].second << '\n';
        }
    }
    for (int i = 2; i <= n; ++i) {
        dist[i] = 1e9;
    }
    s.insert(make_pair(0, 1));
    djkstra();
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == 1e9) {
            dist[i] = 0;
        }
        fout << dist[i] << " ";
    }
    return 0;
}