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

#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));
                }
            }
//        }
    }
}

int main(int argc, const char *argv[]) {
    freopen("dijkstra.in", "r",stdin);
    freopen("dijkstra.out", "w",stdout);
    int n, m, x, y, c;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        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) {
        printf("%d ", ans[i]==INF ? 0: ans[i]);
    }
}