#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

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

vector <pair<int, int>> adj[50001];

int vertices, edges, u, v, weight;
int dist[50001]; bool visited[50001];
const int infinity = 25000001;

void Dijkstra(int source){

    for(int node = 1; node <= vertices; node++){
        dist[node] = infinity;
    }dist[source] = 0;

    priority_queue <pair<int, int> ,vector<pair<int, int>>, compare> Q;
    Q.push(make_pair(source, dist[source]));

    while(Q.empty() == false){

        int u = Q.top().first; Q.pop();

        if(visited[u] == false){
            visited[u] = true;

            for(int i = 0; i < adj[u].size(); i++){

                int v = adj[u][i].first;
                int weight = adj[u][i].second;

                if (dist[v] > dist[u] + weight && visited[v] == false){
                    dist[v] = dist[u] + weight;
                    Q.push(make_pair(v, -dist[v]));
                }
            }
        }
    }
}

int main(){

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

    scanf("%d %d", &vertices, &edges);

    for(int i = 1; i <= edges; i++){
        scanf ("%d %d %d", &u, &v, &weight);
        adj[u].push_back(make_pair(v, weight));
    }Dijkstra(1);

    for(int node = 2; node <= vertices; node++){
        printf("%d ", (dist[node] == infinity) ? 0 : dist[node]);
    }
    return 0;
}