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

const int INF = 1e9;

void dijkstra(int start, vector<vector<pair<int, int>>> &adj, int n, vector<int> &dist)
{
    dist.resize(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty())
    {
        int u = pq.top().second;
        int current_dist = pq.top().first;
        pq.pop();

        if (current_dist > dist[u]) continue;

        for (auto &edge : adj[u])
        {
            int v = edge.first;
            int w = edge.second;

            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

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

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

    vector<vector<pair<int, int>>> adj(n + 1);

    int i, j, c;
    for(int x = 0; x < m; x++)
    {
        fin >> i >> j >> c;
        adj[i].push_back({j, c});
    }
    vector<int> dist;
    dijkstra(1, adj, n, dist);

    for (int node = 2; node <= n; ++node)
    {
        if(dist[node] == INF)
            fout << 0 << " ";
        else
            fout << dist[node] << " ";
    }
    return 0;
}