#include <bits/stdc++.h>

using namespace std;

struct Edge {

    int to;
    long long cost;
};

bool operator <(const Edge &e1, const Edge &e2) {
    return e1.cost < e2.cost;
}

class Graph {

    vector < vector <Edge> > adjList;
    int V, E;

public:

    Graph(const char *Filename) {

        ifstream fin(Filename);

        fin >> this->V >> this->E;
        this->adjList.resize(this->V);

        for(int e = 0; e < this->E; ++e){

            int from, to, cost;
            fin >> from >> to >> cost;

            --from; --to;
            adjList[from].push_back({to, cost});
        }
    }

    vector <long long> Dijkstra(int source) {

        vector <long long> dist(this->V, LLONG_MAX);
        dist[source] = 0;

        set <Edge> RB;
        RB.insert({0, 0});

        while(!RB.empty()) {

            int node = RB.begin()->to;
            int cost = RB.begin()->cost;

            RB.erase(RB.begin());

            for(const Edge &edge : this->adjList[node])
                if(dist[edge.to] > dist[node] + edge.cost){

                    if(RB.count({edge.to, dist[edge.to]}))
                        RB.erase({edge.to, dist[edge.to]});

                    dist[edge.to] = dist[node] + edge.cost;
                    RB.insert({edge.to, dist[edge.to]});
                }
        }

        return dist;
    }
};

int main(){

    Graph graph("../date.in");
    vector <long long> ans = graph.Dijkstra(0);

    ofstream fout("../date.out");
    for(int node = 1; node < (int)ans.size(); ++node)
        if(ans[node] == LLONG_MAX)
            fout << 0 << ' ';
        else fout << ans[node] << ' ';
}