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

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

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

    while (!paths.empty())  {
        int topNode = (paths.begin() -> second);
        int distance = (paths.begin() -> first);
        paths.erase(paths.begin());

        for (pair <int, int> node : edges[topNode])
            if (minCost[node.first] > CURRENTSUM) {
                set <pair <ll, int> > :: iterator it = paths.find(make_pair(minCost[node.first], node.first));
                if (it != paths.end())
                    paths.erase(it);

                paths.insert(make_pair(CURRENTSUM, node.first));
                minCost[node.first] = CURRENTSUM;
            }
    }

}

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 = 1; 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;
}