#include <algorithm>
#include <fstream>
#include <functional>
#include <iterator>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

const int INF = numeric_limits<int>::max();

vector<int> dijkstra(const int source, const vector<vector<pair<int, int>>>& G) {
    vector<int> D(G.size(), INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
        
    D[source] = 0;    
    Q.push(make_pair(0, source));
    
    while (!Q.empty()) {
        pair<int, int> next = Q.top(); Q.pop();
        int u = next.second, d = next.first, v, c;
        
        if (D[u] == d) for (auto& it : G[u]) {
            v = it.first;
            c = it.second;
            if (D[v] > D[u] + c) {
                D[v] = D[u] + c;
                Q.push(make_pair(D[v], v));
            }
        }
    }
    
    return D;
}

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    
    int n, m; fin >> n >> m;
    vector<vector<pair<int, int>>> G(n);
    
    for(int u, v, c; m; --m) {
        fin >> u >> v >> c;
        G[u-1].push_back(make_pair(v-1, c));
    }
    
    vector<int> D = dijkstra(0, G);
    
    transform(D.begin(), D.end(), D.begin(),
              [](const int& x) { return (x != INF) ? x : 0;});
    copy(D.begin() + 1, D.end(), ostream_iterator<int>(fout, " ")), fout << endl;
    
    return 0;
}