#include <bits/stdc++.h>

using namespace std;

const int DIM = 50000 + 5;

vector < pair < int, int > > a[DIM];
vector < int > d(DIM, 2e9);
multiset < pair < int, int > > ms;

void dijkstra(int k, int n)
{
    ms.insert({0, 1});
    d[1] = 0;

    while(!ms.empty()) {
        int k = ms.begin() -> second;

        ms.erase(ms.begin());

        for(auto v : a[k]) {
            int to = v.first;
            int len = v.second;

            if(d[to] > d[k] + len) {
                ms.erase({d[to], to});
                d[to] = d[k] + len;
                ms.insert({d[to], to});
            }
        }
    }

    for(int i = 2; i <= n; ++i) {
        if(d[i] == 2e9) printf("0 ");
        else printf("%d ", d[i]);
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m;

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        int x, y, w;

        scanf("%d%d%d", &x, &y, &w);

        a[x].push_back({y, w});
    }

    dijkstra(1, n);

    return 0;
}