#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[node] + g[node][i].second < dist[g[node][i].first])
            {
                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;
}