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

const int NMAX = 200000;
const int MMAX = 400000;
int N, M;

vector<pair<int, int>> adj[NMAX + 1];
vector<int> dist;

void readInput() {
    ifstream f("dijkstra.in");

    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        int u, v, c;
        f >> u >> v >> c;
        adj[u].push_back({v, c});
    }
    dist = vector<int>(N + 1, INT_MAX);
    f.close();
}

void dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, 1});
    dist[1] = 0;

    while (pq.size()) {
        auto p = pq.top();
        pq.pop();

        int d = p.first, 
            u = p.second;
        
        if (d > dist[u])
            continue;

        for (auto j : adj[u]) {
            if (dist[u] + j.second < dist[j.first])
            {
                dist[j.first] = dist[u] + j.second;
                pq.push({dist[j.first], j.first});
            }
        }
    }
}

void output() {
    ofstream g("dijkstra.out");

    for (int i = 2; i <= N; i++) {
        if (dist[i] == INT_MAX)
            g << -1 << " ";
        else
            g << dist[i] << " ";
    }
    g.close();
}

int main() {
    readInput();
    dijkstra();
    output();
    return 0;
}