#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> i_pair;

#define INF (1 << 15)

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

class Dijkstra {
    int vertices;
    vector<vector<i_pair> > edges;
public:
    Dijkstra(int vertices) {
        this->vertices = vertices;
        this->edges = vector<vector<i_pair> >(vertices + 1);
    }

    void add_edge(int from, int to, int weight) {
        this->edges[from].push_back(make_pair(to, weight));
    }

    vector<int> distances(int from) {
        vector<int> dist(this->vertices + 1, INF);
        priority_queue<int, vector<int>, greater<int>> pq;

        dist[from] = 0;
        pq.push(from);

        while (!pq.empty()) {
            int curr = pq.top();
            pq.pop();

            vector<i_pair>::iterator it = this->edges[curr].begin();
            for (; it != this->edges[curr].end(); it++) {
                int vertex = (*it).first;
                int weight = (*it).second;
                if (dist[vertex] > dist[curr] + weight) {
                    dist[vertex] = dist[curr] + weight;
                    pq.push(vertex);
                }
            }
        }

        return dist;
    }
};


int main() {
    int vertices, edges;
    in >> vertices >> edges;
    Dijkstra *d = new Dijkstra(vertices);
    for (size_t _ = 0; _ < edges; _++) {
        int a, b, c;
        in >> a >> b >> c;
        d->add_edge(a, b, c);
    }

    vector<int> dist = d->distances(1);
    for (size_t i = 2; i <= vertices; i++) {
        out << dist[i] << " ";
    }

    return 0;
}