#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <utility>
#include <set>

#define IN_FILE_NAME "pathbgep.in"
#define OUT_FILE_NAME "pathbgep.out"


class Vertex {
public:
    unsigned long long way_len;
    std::vector< std::pair<int, unsigned int> > child;

    Vertex() : way_len{ std::numeric_limits<unsigned long long>::max() } {

    }

};

long long dijkstraSPF(std::vector<Vertex> &adj_list, int start_v, int finish_v) {
    std::set< std::pair<unsigned long long, int> > queue;
    adj_list[start_v].way_len = 0;
    queue.emplace(0, start_v);

    while(!queue.empty()) {
        auto v_look = *queue.begin();
        queue.erase(queue.begin());

        for (auto &child : adj_list[v_look.second].child) {
            int v_to = child.first;
            unsigned int e_weight = child.second;
            unsigned long long way_len_new = adj_list[v_look.second].way_len + e_weight;

            if (way_len_new < adj_list[v_to].way_len) {
                queue.erase(std::make_pair(adj_list[v_to].way_len, v_to));
                adj_list[v_to].way_len = way_len_new;
                queue.emplace(adj_list[v_to].way_len, v_to);
           }
        }

    }

    return (adj_list[finish_v].way_len == std::numeric_limits<unsigned long long>::max()) ? -1 : adj_list[finish_v].way_len;
}

int main() {
    std::ifstream fin(IN_FILE_NAME);

    int v_count, e_count;
    fin >> v_count >> e_count;

    std::vector<Vertex> adj_list(v_count);
    for (int i = 0; i < e_count; ++i) {
        int e_begin, e_end, e_weight;
        fin >> e_begin >> e_end >> e_weight;
        adj_list[e_begin - 1].child.emplace_back(e_end - 1, e_weight);
        adj_list[e_end - 1].child.emplace_back(e_begin - 1, e_weight);
    }

    fin.close();

    dijkstraSPF(adj_list, 0, 0);

    std::ofstream fout(OUT_FILE_NAME);
    for (auto &item : adj_list) {
        fout << item.way_len << ' ';
    }
    fout.close();

    return 0;
}