#include <cstdio>
#include <utility>
#include <vector>
#include <queue>
#include <fstream>

#define INF 1000000000
using namespace std;
const int MV = 5e4;

int ans[50005];

vector<pair<int, int> > nodes[50005];

void dijkstra(int start) {
    priority_queue<pair<int, int> > pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        if (ans[top.second] != top.first)
            continue;
//        if (ans[top.second] == top.first) {
        ans[top.second] = top.first;
        for (auto node : nodes[top.second]) {
            if (ans[top.second] + node.second < ans[node.first]) {
                ans[node.first] = ans[top.second] + node.second;
                pq.push(make_pair(ans[node.first], node.first));
            }
        }
//        }
    }
}
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.in");
int main(int argc, const char *argv[]) {
//    freopen("dijkstra.in", "r", stdin);
//    freopen("dijkstra.out", "w", stdout);
    int n, m, x, y, c;
    in >> n >>m;
//    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        in >> x >> y >>c;
//        scanf("%d %d %d", &x, &y, &c);
        nodes[x].emplace_back(make_pair(y, c));
//        nodes[y].emplace_back(make_pair(x, c));
    }
    for (int i = 2; i <= n; ++i) {
        ans[i] = INF;
    }
    dijkstra(1);
    for (int i = 2; i <= n; ++i) {
        out << (ans[i] == INF ? 0 : ans[i]) << " ";
//        printf("%d ", ans[i] == INF ? 0 : ans[i]);
    }
}