#include <bits/stdc++.h>

#define FILE "dijkstra"

#ifdef FILE
std::ifstream fin(FILE ".in");
std::ofstream fout(FILE ".out");
#else
#define fin cin
#define fout cout
#endif // FILE

using namespace std;

#define LMax 50005

vector <pair<int, int> > v[LMax];
queue <int> q;
int Values[LMax];
int lung[LMax];
int x, y, n, m, p, l;

void Dijkstra() {
    q.push(1);
    while (!q.empty()) {
        x = q.front();
        q.pop();
        int lim = v[x].size();
        for (int i = 0; i < lim; ++i)
            if (Values[x] + v[x][i].second < Values[v[x][i].first] || Values[v[x][i].first] == -1)
                Values[v[x][i].first] = Values[x] + v[x][i].second, q.push(v[x][i].first);
    }
}

int main() {
    fin >> n >> m;
    fill(Values + 1, Values + n + 1, -1);
    Values[1] = 0;
    for (int i = 1; i <= m; ++i)
        fin >> x >> y >> l, v[x].push_back({y, l});
    Dijkstra();
    for (int i = 2; i <= n; ++i)
        fout << Values[i] << ' ';
    return 0;
}