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

typedef pair<int, int> Pair;
typedef pair<int*, int> PairHeap;

class Comapare {
    public:
    bool operator()(const PairHeap& a, const PairHeap& b) {
        return *a.first < *b.first;
    }
};

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

vector<int> len;
vector<bool> inHeap;

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

void solve(int v) {
    PairHeap aux;
    len[v] = 0;
    heap.push(PairHeap(&len[v], v));
    inHeap[v] = true;

    while(!heap.empty()) {
        aux = heap.top();
        heap.pop();
        inHeap[aux.second] = false;
        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;
                if(!inHeap[e.first]) {
                    heap.push(PairHeap(&len[e.first], e.first));
                    inHeap[e.first] = true;
                }
            }
        }
    }
}

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;
}