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

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

class MinHeap {
public:
    MinHeap(int num_nodes) {
        position_ = vector<int>(num_nodes, kInexistent);
    }
    void Debug() {
        cout << "heap: (" << nodes_.size() << ")" << endl;
        for (int i = 0; i < nodes_.size(); ++i) {
            cout << nodes_[i].first << " " << nodes_[i].second << endl;
        }
        cout << endl;
    }
    int Push(int node, int value) {
        int node_position = position_[node];
        if (node_position == kInexistent) {
            nodes_.push_back(make_pair(node, value));
            node_position = nodes_.size() - 1;
            position_[node] = node_position;
        }
        Up(node_position);
    }
    pair<int,int> Pop() {
        assert(!nodes_.empty());
        pair<int,int> extracted_pair = nodes_.front();
        position_[extracted_pair.first] = kInexistent;
        nodes_[0] = nodes_.back();
        nodes_.pop_back();
        if (!nodes_.empty()) {
            position_[nodes_.front().first] = 0;
            Down(0);
        }
        return extracted_pair;
    }
    bool Empty() {
        return nodes_.empty();
    }
private:
    void Up(int position) {
        while (position > 0) {
            int root_chose = position / 2;
            if (nodes_[root_chose] > nodes_[position]) {
                swap(position_[position], position_[root_chose]);
                swap(nodes_[position], nodes_[root_chose]);
            }
            position = root_chose;
        }
    }
    void Down(int position) {
        while (position < nodes_.size()) {
            int left_sub_node = 2 * position + 1;
            int right_sub_node = 2 * position + 2;
            int best_chose = left_sub_node;
            if (right_sub_node < nodes_.size() && nodes_[right_sub_node].second < nodes_[right_sub_node].second) {
                best_chose = right_sub_node;
            }
            if (best_chose < nodes_.size()) {
                swap(position_[position], position_[best_chose]);
                swap(nodes_[position], nodes_[best_chose]);
            }
            position = best_chose;
        }
    }
    vector<pair<int, int>> nodes_;
    vector<int> position_;
    const int kInexistent = -1;
};

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;
        MinHeap min_heap(num_nodes_);
        min_heap.Push(0, 0);
        while (!min_heap.Empty()) {
            pair<int,int> best_pair = min_heap.Pop();
            int best_node = best_pair.first;
            // cout << best_node.first <<" " << best_node.first <<endl;
            for (int i = 0; i < edge_list_[best_node].size(); ++i) {
                int neighbour = edge_list_[best_node][i].end_node;
                // cout << "neighbour: " << neighbour << endl;
                int cost = edge_list_[best_node][i].cost;
                if (min_distance_[neighbour] > min_distance_[best_node] + cost) {
                    min_distance_[neighbour] = min_distance_[best_node] + cost;
                    min_heap.Push(neighbour, min_distance_[neighbour]);
                } 
            }
            // min_heap.Debug();
        }
    }
    vector<int> GetDistances() {
        vector<int> distances(min_distance_.begin()+1, min_distance_.end());
        for (int i = 0; i < distances.size(); ++i) {
            if (distances[i] == kUndef) {
                distances[i] = 0;
            }
        }
        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;

}