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

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define MAX 50010
#define mp make_pair
#define INF 1000000000

priority_queue<pair<double, int> > Q;
vector<pair<int, int> > G[MAX];
int dist[MAX], calc[MAX];
int main() {
    int n, m, i, x, y, c, node;
    fin >> n >> m;
    for(i = 1 ; i <= m ; i++) {
        fin >> x >> y >> c;
        G[x].push_back(mp(y, c));
    }
    for(i = 1 ; i <= n ; i++) {
        dist[i] = INF;
    }
    dist[1] = 0;
    Q.push(mp(0, 1));
    while(Q.size()) {
        pair<double, int> p = Q.top();
        Q.pop();
        node = p.second;
        if(calc[node])
            continue;
        calc[node] = true;
        for(auto x : G[node]) {
            if(dist[x.first] > dist[node] + x.second) {
                dist[x.first] = dist[node] + x.second;
                Q.push(mp(-dist[x.first], x.first));
            }
        }
    }
    for(i = 2 ; i <= n ; i++) {
        if(dist[i] == INF)
            dist[i] = -1;
        fout << dist[i] << " ";
    }
    fout << endl;
}