#include <bits/stdc++.h>
#define ll long long
#define NEWCOST node.second + currentDistance
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, x, y, c;
vector <pair <int, int> > edges[50001];
ll minCost[50001];

void findPaths() {
    priority_queue <pair <ll, int> > paths;
    paths.push(make_pair(0, 1));

    while (!paths.empty()) {
        int currentNode = paths.top().second;
        ll currentDistance = -paths.top().first;
        paths.pop();

        for (pair <int, int> node : edges[currentNode])
            if (NEWCOST < minCost[node.first]) {
                minCost[node.first] = NEWCOST;
                paths.push(make_pair(-(NEWCOST), node.first));
            }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        edges[x].push_back(make_pair(y, c));
    }

    for (int i = 2; i <= n; i++)
        minCost[i] = LLONG_MAX;
    findPaths();

    for (int i = 2; i <= n; i++)
        if (minCost[i] == LLONG_MAX)
            fout << "0 ";
        else
            fout << minCost[i] << " ";

    return 0;
}