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

#define inf 200000000

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

vector<vector<pair<int,int>>> graf;
vector<int> d, tata;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

void dijkstra(int n, int m, int s) {
    d.assign(n, inf); d[s] = 0;
    tata.assign(n, 0); tata[s] = -1;

    q.push({d[s], s});
    while(!q.empty()) {
        pair<int, int> u = q.top();
        q.pop();

        if (u.first != d[u.second]) { continue; }
        for (pair<int, int> m : graf[u.second]) {
            if (d[m.first] > d[u.second] + m.second) {
                d[m.first] = d[u.second] + m.second;
                tata[m.first] = u.second;
                q.push({d[m.first], m.first});
            }
        }
    }
}

int main() {
    int n, m; fin >> n >> m;
    graf.resize(n);

    for (int i = 0; i < m; i++) {
        int x, y, c; fin >> x >> y >> c; x--; y--;
        graf[x].push_back(pair<int,int>(y, c));
    }

    dijkstra(n, m, 0);

    for (int u = 0; u < n; u++) {
        if (tata[u]+1 != 0) {
            fout << ((d[u] == inf) ? 0 : d[u]) << " ";
        }
    }

    return 0;
}