#include <bits/stdc++.h>

#define NMAX 50001
#define INF 1 << 30

#define pb push_back
#define mp make_pair

using namespace std;

struct compare {
	bool operator()(const pair<int, int> &x, const pair<int, int> &y) const {
        return x.second > y.second;
	}
};

char visited[NMAX];
int N, M, dist[NMAX];
vector< pair<int, int> > graph[NMAX];
priority_queue< pair<int, int>, vector< pair<int, int> >, compare > q;


void dijkstra(int start) {
    pair<int, int> curr;

    for (int it = 1; it <= N; ++it) dist[it] = INF;

    dist[start] = 0;
    q.push(mp(start, 0));

    while (!q.empty()) {
        curr = q.top(); q.pop();
        while (visited[curr.first]) {
            curr = q.top(); q.pop();
        }
        visited[curr.first] = 1;

        for (int it = 0; it < (int) graph[curr.first].size(); ++it) {
            if (!visited[graph[curr.first][it].first] && dist[graph[curr.first][it].first] > dist[curr.first] + graph[curr.first][it].second) {
                dist[graph[curr.first][it].first] = dist[curr.first] + graph[curr.first][it].second;
                q.push(mp(graph[curr.first][it].first, dist[graph[curr.first][it].first]));
            }
        }
    }
}

int main() {
    int x, y, c;

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

    scanf("%d%d", &N, &M);

    for (int it = 0; it < M; ++it) {
        scanf("%d%d%d", &x, &y, &c);
        graph[x].pb(mp(y, c));
    }

    dijkstra(1);

    for (int it = 2; it <= N; ++it)
        printf("%d ", dist[it] == INF ? 0 : dist[it]);

    return 0;
}