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

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

const int MAX_SIZE = 5 * 1e4, INF = 1e9;
int n, m;
vector<pair<int, int>> graph[MAX_SIZE]; //stochez si costul fiecarui arc
vector<int> distances(MAX_SIZE + 1, INF);
vector<bool> visited(MAX_SIZE + 1);

struct compareDistances {
    bool operator() (int firstNod, int secondNod) {
        return distances[firstNod] > distances[secondNod];
    }
};
priority_queue<int, vector<int>, compareDistances> currentNodes;


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

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