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

typedef pair<int, int> Pii;

const int infinit = INT_MAX / 2;

void dijkstra(
    int start, int n,
    const vector<vector<Pii>> &adj,
    vector<int> &dist)
{
    priority_queue<Pii, vector<Pii>, greater<Pii>> q;
    dist[start] = 0;
    q.push({0, start});

    while (!q.empty()) {
        int d = q.top().first;
        int v = q.top().second;
        q.pop();

        if (dist[v] != d)
            continue;

        for (auto p : adj[v]) {
            int vecin = p.first;
            int cost = p.second;

            if (dist[vecin] > d + cost) {
                dist[vecin] = d + cost;
                q.push({dist[vecin], vecin});
            }
        }
    }
}




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

    int n, m;
    fin >> n >> m;

    vector<vector<Pii>> adj(n+1);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        fin >> a >> b >> c;

        adj[a].push_back({b,c});
    }

    vector<int> dist(n+1, infinit);
    dijkstra(1, n, adj, dist);

    for (int i = 2; i <= n; i++)
        if (dist[i] == infinit)
            fout << 0 << " ";
        else
            fout << dist[i] << " ";

    fout << endl;
    return 0;
}