#include <bits/stdc++.h>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

const int INF = 1e9;
int n, m;
vector <pair<int, int>> g[100001];
int dist[100001];

void dijkstra(int source)
{
    for (int node = 2; node <= n; node++)
        dist[node] = INF;

    priority_queue<pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source});
    while (!pq.empty())
    {
        int cost = pq.top().first, node = pq.top().second;
        pq.pop();

        if (cost != dist[node])
            continue;

        for (int i = 0; i < g[node].size(); i++)
        {
            if (dist[g[node][i].first] < dist[node] + g[node][i].second)
                continue;
            dist[g[node][i].first] = dist[node] + g[node][i].second;
            pq.push({dist[g[node][i].first], g[node][i].first});
        }
    }
    for (int i = 2; i <= n; i++)
        if (dist[i] == INF)
            dist[i] = 0;

}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        g[x].push_back({y, cost});
    }

    dijkstra(1);
    for (int node = 2; node <= n; node++)
        fout << dist[node] << ' ';
    return 0;
}