#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <queue>

std::ifstream djkin("dijkstra.in");
std::ofstream djkout("dijkstra.out");

using namespace std;

class Link {
private:
    unsigned from;
    unsigned to;
    double cost;
public:
    Link(unsigned from, unsigned to, double cost): from(from), to(to), cost(cost) {}
    unsigned getTo() {
        return this->to;
    }

    double getCost() {
        return this->cost;
    }

};


class Graph {
private:
    unsigned V;
    std::list<Link> *adj;

public:
    Graph(unsigned V): V(V) {
        adj = new std::list<Link>[V + 1];
    }

    void addEdge(unsigned from, unsigned to, double cost) {
        Link first_link(from, to, cost);
        adj[from].push_back(first_link);
    }

    void shortestPath(unsigned start) {
        std::priority_queue<std::pair<double, unsigned>, std::vector<std::pair<double, unsigned>>, std::greater<>> pq;
        std::vector<double> dist(this->V + 1, UINT_MAX);

        pq.push(std::make_pair(0, start));
        dist[start] = 0;

        while(!pq.empty()) {
            unsigned v = pq.top().second;
            pq.pop();
            for(auto it : adj[v]) {
                unsigned u = it.getTo();
                double cost = it.getCost();
                if (dist[u] > dist[v] + cost) {
                    dist[u] = dist[v] + cost;
                    pq.push(std::make_pair(dist[u], u));
                }
            }
        }
        for (unsigned i = 2; i <= this->V; ++i)
            djkout << dist[i] << " ";
    }

};


int main() {
    unsigned long n, m, a, b, c;
    djkin >> n >> m;
    auto G = new Graph(n);
    for (unsigned i = 0; i < m; i ++) {
        djkin >> a >> b >> c;
        G->addEdge(a, b, c);
    }
    G->shortestPath(1);

    return 0;
}