#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
using namespace std;
 
#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif

struct Edge {
    int start_node, end_node, cost;
};

class Dijkstra {
public:
    Dijkstra(int num_nodes) : num_nodes_(num_nodes) {
        edge_list_.resize(num_nodes_);
        min_distance_.resize(num_nodes_, kUndef);
    }
    void AddEdge(const Edge& edge) {
        edge_list_[edge.start_node].push_back(edge);
    }
    void CalculateMinDistances() {
        min_distance_[0] = 0;
        vector<pair<int,int>> min_heap;
        min_heap.push_back(make_pair(0,0));
        push_heap(min_heap.begin(), min_heap.end());
        while (!min_heap.empty()) {
            pair<int,int> best_node = min_heap[0];
            //cout << best_node.first <<" " << best_node.second <<endl;
            pop_heap(min_heap.begin(), min_heap.end());
            min_heap.pop_back();
            for (int i = 0; i < edge_list_[best_node.second].size(); ++i) {
                int neighbour = edge_list_[best_node.second][i].end_node;
                //cout << "neighbour: " << neighbour << endl;
                int cost = edge_list_[best_node.second][i].cost;
                if (min_distance_[neighbour] > min_distance_[best_node.second] + cost) {
                    min_distance_[neighbour] = min_distance_[best_node.second] + cost;
                    min_heap.push_back(make_pair(min_distance_[neighbour], neighbour));
                    push_heap(min_heap.begin(), min_heap.end());
                } 
            }
        }
    }
    vector<int> GetDistances() {
        vector<int> distances(min_distance_.begin()+1, min_distance_.end());
        return distances;
    }

private:
    const int kUndef = 0xFFFFFFF;
    int num_nodes_, num_edges_;
    vector<vector<Edge>> edge_list_;
    vector<int> min_distance_;
}; 
 
int main() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    int num_nodes, num_edges;  
    int start_node, end_node, edge_cost;
    scanf("%d %d", &num_nodes, &num_edges);

    Dijkstra * instance = new Dijkstra(num_nodes);

    for (int i = 0; i < num_edges; ++i) {
        scanf("%d %d %d", &start_node, &end_node, &edge_cost);
        instance->AddEdge({start_node-1, end_node-1, edge_cost});
    }

    instance->CalculateMinDistances();
    for (const auto& distance : instance->GetDistances()) {
        printf("%d ", distance);
    }

    return 0;

}