#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> Pair;

int V, E;
vector<vector<Pair>> edges;
priority_queue<Pair, vector<Pair>, less<Pair>> heap;

vector<int> len;

void read() {
    int v, v1, c;
    cin >> V >> E;
    edges.resize(V);
    len.resize(V, -1);
    for (int i = 0; i < E; ++i) {
        cin >> v >> v1 >> c;
        edges[v - 1].push_back(Pair(v1 - 1, c));
    }
}

void solve(int v) {
    Pair aux;
    len[v] = 0;
    heap.push(Pair(0, v));

    while(!heap.empty()) {
        aux = heap.top();
        heap.pop();
        for (auto e : edges[aux.second]) {
            if (len[e.first] == -1 ||
                len[e.first] > aux.first + e.second) {
                len[e.first] = aux.first + e.second;
                heap.push(Pair(len[e.first], e.first));
            }
        }
    }
}

void write() {
    for (int i = 1; i < len.size(); ++i) {
        cout << len[i] << " ";
    }
    cout << endl;
}

int main()
{
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
    read();
    solve(0);
    write();
    return 0;
}