#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct elem {
    int dist, x;
    bool operator < (const elem &aux) const {
        if (dist != aux.dist) return dist < aux.dist;
        return x < aux.x;
    }

    bool operator > (const elem &aux) const {
        if (dist != aux.dist) return dist > aux.dist;
        return x > aux.x;

    }
};

const int nmax = 5e4 + 5;
int n, m, ans[nmax];
vector <pair <int, int> > v[nmax];
bool marked[nmax];

int main()
{
    fin >> n >> m;
    int i, j, dist;
    for (int k = 1; k <= m; ++k) {
        int i, j, dist;
        fin >> i >> j >> dist;
        v[i].push_back({j, dist});
    }

    int p = 1;
    for (int i = 1; i <= n; ++i) {
        if (i != p) ans[i] = 1e9;
    }

    priority_queue <elem, vector <elem>, greater <elem> > q;
    q.push({0, p});
    while (!q.empty()) {
        int nr = q.top().x;
        q.pop();
        if (marked[nr]) continue;

        marked[nr] = true;
        for (pair <int, int> i : v[nr]) {
            if (ans[nr] + i.second < ans[i.first]) {
                ans[i.first] = ans[nr] + i.second;
                q.push({ans[i.first], i.first});
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (ans[i] != 1e9) fout << ans[i] << ' ';
        else fout << -1 << ' ';
    }
    return 0;
}