#include <bits/stdc++.h>

#define INF 1 << 30
#define NMAX 50001

using namespace std;

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

int n, p;

vector< pair<int, int> > vecini[NMAX];
vector<int> cost;
queue<int> q;

void initCost(){
    cost = vector<int>(n + 1, INF);
}

void bf(int nod){
    cost[nod] = 0;
    q.push(nod);
    while(!q.empty()){
        int k = q.front();
        q.pop();
        for(auto vecin : vecini[k])
            if(cost[vecin.first] > cost[k] + vecin.second){
                cost[vecin.first] = cost[k] + vecin.second;
                q.push(vecin.first);
            }
    }
}

int main()
{
    f >> n >> p;
    int x, y, c;
    while(f >> x >> y >> c){
        vecini[x].push_back(make_pair(y, c));
    }
    initCost();
    bf(1);
    for(int i = 2; i <= n; i ++)
        if(cost[i] == INF) cost[i] = -1;
    for(int i = 2; i <= n; i ++)
        g << cost[i] << " ";
    return 0;
}