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

using namespace std;

typedef pair<int, int> i_pair;

#define INF (1 << 15)
#define MAX_V 50001

int vertices, edges, dist[MAX_V];
vector<i_pair> graph[MAX_V];
bool visited[MAX_V];

struct cmp {
    bool operator()(const int &a, const int &b) {
        return dist[a] > dist[b];
    }
};

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

void solve(int from) {
    for (size_t i = 0; i < MAX_V; i++) {
        dist[i] = INF;
    }

    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[curr] = false;
        vector<i_pair>::iterator it = graph[curr].begin();
        for (; it != graph[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]) {
                    visited[vertex] = true;
                    pq.push(vertex);
                }
            }
        }
    }
}

int main() {
    in >> vertices >> edges;
    for (size_t _ = 0; _ < edges; _++) {
        int a, b, c;
        in >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }

    solve(1);

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

    return 0;
}