#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");

vector<int> dist;

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));
    }

    void distances(int from) {
        bool visited[this->vertices];
        dist = vector<int>(this->vertices, INF);
        struct cmp {
            bool operator()(const int &a, const int &b) {
                return dist[a] > dist[b];
            }
        };
        priority_queue<int, vector<int>, cmp> pq;


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

        while (!pq.empty()) {
            int curr = pq.top();
            pq.pop();
            visited[from] = false;
            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;
                    if (!visited[vertex]) {
                        pq.push(vertex);
                        visited[vertex] = true;
                    }
                }
            }
        }
    }
};


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);
    }

    d->distances(1);
    for (size_t i = 2; i <= vertices; i++) {
        if (dist[i] != INF)
            out << dist[i] << " ";
        else
            out << "0 ";
    }

    return 0;
}