// Copyright Radu Nichita 2020 [email protected] 	

#include <bits/stdc++.h>
#define NMAX 50009
#define kINF (1<<30)
#define NO_PARENT -1

using namespace std;
	
class Task {

    int N, M, source;;
    
    std::priority_queue<pair<int, int>, vector<pair<int, int>>,
                greater<pair<int, int>>> pq;
    
    std::vector<std::pair<int, int>> matrix[NMAX];
    std::vector<int> distances;

 
	
    void read_input() {
        int src, dst, cost;
        std::ifstream in("dijkstra.in");
        in >> N >> M; // dimensiune graf 
        distances = std::vector<int>(N + 1, kINF);
        for (int i = 1; i <= M; i++) {
            in >> src >> dst >> cost;
            matrix[src].push_back({cost, dst});
        }

        source = 1;

        in.close();
    }
	
 
	
    void getResult() {
        Dijkstra(source);
    }


    void Dijkstra(int source) {
        distances[source] = 0;
        pq.push({distances[source], source});
        while (!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            int cost = top.first;
            int node = top.second;
            if (cost > distances[node]) {
                continue;
            }
            for (auto const &neigh: matrix[node]) {
                int neighbour = neigh.second;
                int cost_edge = neigh.first;
                if (distances[neighbour] > distances[node] + cost_edge) {
                    distances[neighbour] = distances[node] + cost_edge;
                    pq.push({distances[neighbour], neighbour});
                }
            }
        }
    }
	
 
	
    void print() {
        std::ofstream out("dijkstra.out");   
        for (int i = 1; i <= N; i++) {
            if (i != source) {
                out<<(distances[i] == kINF ? 0 : distances[i])<<" ";
            }
        }
        out<<"\n";
        out.close();
        return;
    }
	
 
	
 public:
	
    void solve() {
        read_input();
        Dijkstra(source);
        print();
    }
	
 
	
};
	
 
	
int main() {

    Task* task = new Task();
	
    task->solve();
	
    delete(task);
	
 
	
    return 0;
	
}