#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define pii pair<int, int>

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

const int NMAX = 5 * 1e5 + 5;
const int inf = 1e9;
vector <pii> g[NMAX];
int dist[NMAX], visited[NMAX];

void blf(int source, int n) {
    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
    }

    dist[source] = 0;
    visited[source] = 1;
    queue<int> q;
    q.push(source);

    while (!q.empty()) {
        int curr_node = q.front();
        q.pop();

        visited[curr_node] = 0;

        for (auto neigh : g[curr_node]) {
            if (dist[neigh.first] > dist[curr_node] + neigh.second) {
                dist[neigh.first] = dist[curr_node] + neigh.second;
                if (visited[neigh.first] == 0) {
                    q.push(neigh.first);
                    visited[neigh.first] = 1;
                }
            }
        }
    }
}

int main() {
    int n, m;

    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x].push_back({y, z});
    }

    blf(1, n);

    for (int i = 2; i <= n; i++) {
        cout << dist[i] << " ";
    }

    return 0;
}