#include <bits/stdc++.h>

#define nmax 50001

using namespace std;

vector < pair <int, int> > v[ nmax ];
priority_queue <pair <int, int>, vector < pair<int, int> >, greater< pair<int, int> > > q;

void solve(int n, int *dist);

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int n, m;
    cin >> n >> m;

    int dist[ n ];
    for (int i = 2; i <= n; ++i)
        dist[ i ] = INT_MAX;

    for (int i = 0, x, y, z; i < m; ++i) {
        cin >> x >> y >> z;
        v[ x ].push_back({y, z});
    }

    solve(n, dist);

    for (int i = 2; i <= n; i++)
        cout << (dist[ i ] == INT_MAX ? 0 : dist[ i ]) << " ";

}

void solve(int n, int *dist) {
    q.push({0, 1});

    while (!q.empty()) { 
        int cost = q.top().first;
        int nod = q.top().second;
        q.pop();

        if (cost > dist[ nod ])
            continue;

        for (auto arr : v[ nod ]) {
            if (dist[ arr.first ] > cost + arr.second) {
                dist[ arr.first ] = cost + arr.second;
                q.push({dist[arr.first], arr.first});
            }
        }
    }
}