#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]) {
            if (q.empty()) return;
            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;
}