#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

#define MAX_NODES 50000
#define INF 999999999

std::vector<std::pair<int, int> > adj_list[MAX_NODES + 1];
int dist[MAX_NODES + 1];
int parent[MAX_NODES + 1];
int sel[MAX_NODES + 1];

void dijkstra(int num_nodes) {
    std::queue<int> q;
    int u;
    sel[1] = 1;
    
    for (int i = 2; i <= num_nodes; i++) {
        dist[i] = INF;
    }
    
    for (auto &adj_node : adj_list[1]) {
        dist[adj_node.first] = adj_node.second;
        parent[adj_node.first] = 1;
        q.push(adj_node.first);
    }
    
    while (!q.empty()) {
        u = q.front();
        q.pop();
        sel[u] = 1;
        
        for (auto &adj_node : adj_list[u]) {
            if (!sel[adj_node.first] && dist[adj_node.first] > dist[u] + adj_node.second) {
                dist[adj_node.first] = dist[u] + adj_node.second;
                parent[adj_node.first] = u;
            }
        }
    }
    
}

int main(void) {
    FILE * fin = fopen("dijkstra.in", "r");
    FILE * fout = fopen("dijkstra.out", "w");
    
    int n, m, c, x, y;
    
    fscanf(fin, "%d%d", &n, &m);
    
    for (int i = 0; i < m; i++) {
        fscanf(fin, "%d%d%d", &x, &y, &c);
        adj_list[x].push_back(std::make_pair(y, c));
    }
    
    dijkstra(n);
    
    for (int i = 2; i <= n; i++) {
        fprintf(fout, "%d ", dist[i]);
    } 
    
    fclose(fin);
    fclose(fout);
}