#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("dijkstra.in");
//ifstream in("bellmanford.in");
ofstream out("dijkstra.out");
//ofstream out("bellmanford.out");

const int N_MAX = 1e5 + 5, oo = 2e9;
int N, M, InQ[N_MAX], dist[N_MAX];
vector < pair <int, int > > G[N_MAX];
queue < int > q;

void bellman_ford(int node){
    q.push(node); InQ[node] = 1;
    while (!q.empty()){
        int node = q.front(); q.pop(); InQ[node] = 0;
        for (auto vecin : G[node]){
            int v = vecin.first, cost = vecin.second;
            if (!InQ[v]){
                if (dist[v] > dist[node] + cost){
                    dist[v] = dist[node] + cost;
                    q.push(v); InQ[v] = 1;
                }
            }
        }
    }
}

int main(){
    in >> N >> M;
    for (int i = 1; i <= N; ++i){
        int x, y, z; in >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
    }
    for (int i = 2; i<= N; ++i)
        dist[i] = oo;
    bellman_ford(1);
    for (int i = 2; i <= N; ++i)
        out << dist[i] << " ";
    return 0;
}