#include <bits/stdc++.h>
using namespace std;

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

const int MAX_SIZE = 5 * 1e4;
int n, m;
vector<pair<int, int>> graph[MAX_SIZE + 1];
vector<int> distances(MAX_SIZE + 1, INT_MAX);
vector<bool> visited(MAX_SIZE + 1);

void findMinCost(int start) {
    priority_queue<int, vector<int>> currentNodes;
    distances[start] = 0;
    currentNodes.push(start);
    visited[start] = true;
    while (!currentNodes.empty()) {
        int currentNode = currentNodes.top();
        currentNodes.pop();
        visited[currentNode] = false;
        for (const pair<int, int>& nextElement : graph[currentNode]) {
            int nextNode = nextElement.first;
            int cost = nextElement.second;
            if (distances[currentNode] + cost < distances[nextNode]) {
                distances[nextNode] = distances[currentNode] + cost;
                if (!visited[nextNode]) {
                    currentNodes.push(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, distance;
        fin >> x >> y >> distance;
        graph[x].push_back(make_pair(y, distance));
    }
    findMinCost(1);
    for (int i = 2; i <= n; ++i) {
        if (distances[i] == INT_MAX) {
            fout << "0 ";
        } else {
            fout << distances[i] << " ";
        }
    }
    return 0;
}