#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

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

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

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

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        adj[a].push_back({b,c});
    }

    int start = 1;
    vector<int> dist(n+1, INF);
    priority_queue<pair<int,int>, deque<pair<int,int>>, greater<pair<int,int>>> q;

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

    while (!q.empty())
    {
        auto p = q.top();
        q.pop();

        if (p.first == dist[p.second])
            for (auto pv : adj[p.second])
                if (dist[pv.first] > p.first + pv.second)
                {
                    dist[pv.first] = p.first + pv.second;
                    q.push({dist[pv.first], pv.first});
                }
    }

    for (int i = 2; i <= n; ++i)
        fout << (dist[i] == INF ? 0 : dist[i]) << ' ';
    fout << "\n";

    return 0;
}