#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

using namespace std;

int main() {
    int n, k, nl, q, x, y, c, dst, d2, m;
    const int INF = 50000001;
    long long sum;
    
    
    ifstream myfile;
    myfile.open ("dijkstra.in");
    myfile>>n>>m;
    //myfile>>m;
    vector <vector<pair<int, int> > > ad(n);
    vector <int> d(n, INF);
    //vector <int> viz(n, 0);
    //viz[0] = 1;
    d[0] = 0;
    priority_queue <pair<int, int>, vector<pair<int,int> >, greater <pair<int, int> > > pq;
    pair <int, int> pa;
    //set <pair<int, int> > ::iterator it;
    pq.push(make_pair(0, 0));
    
    for (int i = 0; i < m; i++) {
        myfile>>x>>y>>c;
        ad[x-1].push_back(make_pair(y-1, c));
    }
    myfile.close();
    
    while (!pq.empty()) {
        pa = pq.top();
        pq.pop();
        dst = pa.first;
        x = pa.second;
        for (int i = 0; i < ad[x].size(); i++) {
            y = ad[x][i].first;
            d2 = ad[x][i].second + dst;
            if (d[y] > d2) {
                d[y] = d2;
                pq.push(make_pair(d[y], y));
            }
        }
    }
    
    ofstream f2;
    f2.open ("dijkstra.out");
     for (int i = 1; i < n; i++) {
        if (d[i] == INF)
            d[i] = 0;
        f2<<d[i]<<" ";
     }
        f2<<endl;
    f2.close();
       
    return 0;
}