#include <bits/stdc++.h>
#include <queue>
#include <utility>

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

#define inf 1000000000
int n, m;
std::vector<std::pair<int, int>> nums[50001];
std::vector<int> dist(50001);
std::vector<int> viz(50001);

int main()
{
    fin >> n >> m; 
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        nums[x].push_back({y,c});
    }
    
    std::priority_queue<std::pair<int, int>> q;
    dist.assign(50001, inf);
    q.push({0,1});
    dist[1] = 0;

    while(!q.empty())
    {
        int node = q.top().second; q.pop();
        if(viz[node]) continue;
        viz[node] = 1;
        for(auto v : nums[node])
        {
            if(dist[v.first] > dist[node] + v.second)
            {
                dist[v.first] = dist[node] + v.second;
                q.push({-dist[v.first], v.first});
            }
        }
    }

    for(int i = 2; i <= n; i++) 
    {
        fout << dist[i] << ' ';
    }

}