#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

// distance + node
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

vector<vector<pair<int, int>>> G;
vector<int> distances;
int n, m;

void read() {
    f>>n>>m;
    G.resize(n + 1);
    distances.resize(n + 1, INT_MAX);

    int x, y, w;
    while(f>>x>>y>>w) {
       G[x].push_back(make_pair(y, w));
    }
}

void Dijkstra(){
    pq.push(make_pair(0, 1));
    while(pq.size()) {
        int g = pq.top().first;
        int crt = pq.top().second;
        pq.pop();

        if(distances[crt] != INT_MAX)
            continue;

        distances[crt] = g;

        for(auto a : G[crt])
            if(distances[a.first] == INT_MAX)
                pq.push(make_pair(g + a.second, a.first));
    }

    for(int i = 2; i < n + 1; i++) {
        if(distances[i] == INT_MAX)
                distances[i] = 0;
        g<<distances[i]<<' ';
    }

}
int main()
{
    read();
    Dijkstra();
    f.close();
    g.close();
    return 0;
}