#include <bits/stdc++.h>
#define ll long long
#define CURRENTSUM top.first + cost[top.second][node]
using namespace std;

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

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

    while (!paths.empty())  {
        pair <ll, int> top = *paths.begin();
        paths.erase(paths.begin());

        for (int node : edges[top.second])
            if (!reached[node]) {
                paths.insert(make_pair(CURRENTSUM, node));
                if (!minCost[node])
                    minCost[node] = CURRENTSUM;
                minCost[node] = min(minCost[node], CURRENTSUM);
            }
    }

}

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

    findPaths();

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

    return 0;
}