#include <algorithm>
#include <fstream>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>

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

const int NMAX = 50005;
const int INF = 0x3f3f3f3f;

vector< vector< pair<int,int> > > Graph;
vector<int> distanceTo;

void dijkstra(unsigned int n, unsigned int startNode = 1){
    distanceTo = vector<int>(n, INF);

    distanceTo[1] = 0;
    set< pair<int, int> > h;
    h.insert(make_pair(0, 1));
    while (!h.empty()) {
        int node = h.begin()->second;
        int d = h.begin()->first;
        h.erase(h.begin());

        for (auto &it : Graph[node]) {
            int to = it.first;
            int cost = it.second;
            if (distanceTo[to] > distanceTo[node] + cost) {
                if (distanceTo[to] != INF) {
                    h.erase(h.find(make_pair(distanceTo[to], to)));
                }

                distanceTo[to] = distanceTo[node] + cost;
                h.insert(make_pair(distanceTo[to], to));
            }
        }
    }
}

int main() {
    unsigned int n, m;
    fin >> n >> m;
    Graph = vector<vector<pair<int,int> > >(n+1);

    for (int i = 0; i < m; i++) {
        int from, to, cost;
        fin >> from >> to >> cost;

        Graph[from].emplace_back(to, cost);
    }

    dijkstra(n);

    for (int i = 2; i <= n; ++i) {
        if (distanceTo[i] == INF)
            distanceTo[i] = 0;
        fout << distanceTo[i] << ' ';
    }

    fout << '\n';
}