#include <bits/stdc++.h>
#define inf 1000000000
using namespace std;

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


/// .first = cost, .second = adj node
vector<pair<int,int>> e[50010];
priority_queue<pair<int,int>> pq;

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

    bitset<50010> viz;
    vector<int> dist(n+1,inf);
    dist[1] = 0;
    pq.push({0,1});
    while(!pq.empty())
    {
        int node = pq.top().second;
        pq.pop();
        if(viz[node])
            continue;
        viz[node] = 1;
        for(auto adj_pair : e[node])
        {
            int adj = adj_pair.second;
            int len = adj_pair.first;
            if(dist[node] + len < dist[adj])
            {
                dist[adj] = dist[node] + len;
                pq.push({-dist[adj],adj});
            }
        }
    }
    for(int i = 2; i<=n; i++)
        fout << dist[i] << ' ';
    return 0;
}