#include <bits/stdc++.h>
using namespace std;
vector<int> dijkstra(int n, int source, vector<vector<pair<int, int>>> graph)
{
    priority_queue<pair<int, int>> p;
    const int INF = 2e9;
    vector<int> dist(n + 1, INF);
    p.push({-0, source});
    dist[source] = 0;
    while(!p.empty())
    {
        int c = -p.top().first;
        int k = p.top().second;
        p.pop();
        if(c != dist[k])
            continue;
        for(auto it = graph[k].begin(); it != graph[k].end(); it++)
        {
            if(dist[(*it).first] > dist[k] + (*it).second)
            {
                dist[(*it).first] = dist[k] + (*it).second;
                p.push({-dist[(*it).first], (*it).first});
            }
        }
    }
    return dist;
}
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 5);
    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        graph[x].push_back({y, c});
    }
    vector<int> dist;
    dist = dijkstra(n, 1, graph);
    for(auto it = dist.begin() + 2; it != dist.end(); it++)
    {
        cout << (*it) << " ";
    }
}