#include <bits/stdc++.h>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int NMAX = 5e4;
const int MMAX = 25e4;
const int INF = 2e9;

vector<pair<int, int>> graph[NMAX+1];
int rez[NMAX+1];

void dijkstra(int s){
    set<pair<int, int>> q;
    q.insert({0, s});
    rez[s] = 0;
    while(!q.empty()){
    
        int node = q.begin()->second;
        q.erase(q.begin());
        for (vector<pair<int, int>>::iterator it = graph[node].begin(); it != graph[node].end(); ++it) {
            int to = it->first;
            int cost = it->second;
            if (rez[to] > rez[node] + cost) {
                if (rez[to] != INF) {
                    q.erase(q.find(make_pair(rez[to], to)));
                }
                rez[to] = rez[node] + cost;
                q.insert(make_pair(rez[to], to));
            }
        }
    }
}

int main()
{
    fill(rez+1, rez+1+NMAX, INF);
    int n, m;
    f >> n >> m;
    for(int i=1; i<=n; i++){
        int a, b, c;
        f >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }
    
    dijkstra(1);
    for(int i=2; i<=n; i++)
        if(rez[i] == INF)
            g << 0 << ' ';
        else g << rez[i] << ' ';
    g << endl;
    return 0;
}