#include <iostream>
#include <fstream>
#include <map>
#include <climits>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> paer;

int d[50001];
bool viz[50001];

bool comp(int a, int b) {
    return d[a] > d[b];
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m, i, j, a, b, c;
    in>>n>>m;

    map<int, list<paer>> vecini;
    list<paer>::iterator it;

    std::fill(d, d+n+1, INT_MAX);
    d[1] = 0;

    for (i=0; i<m; i++) {
        in>>a>>b>>c;
        vecini[a].push_back(paer(b, c));
    }

    int indici[n+1];
    for (i=1; i<=n; i++) {
        indici[i] = i;
    }
    vector<int> v(indici+1, indici+n+1);

    make_heap(v.begin(), v.end(), comp);

    for (i=0; i<n; i++) {
        int min = v.front();
        while (viz[min]) {
            pop_heap(v.begin(), v.end(), comp); v.pop_back();
            min = v.front();
        }

        viz[min] = 1;
        for (it = vecini[min].begin(); it != vecini[min].end(); it++) {
            b = (*it).first;
            c = (*it).second;

            if (d[b] > d[min] + c) {
                d[b] = d[min] + c;
            }
        }
        make_heap(v.begin(), v.end(), comp);
    }

    for (i=2; i<=n; i++) {
        if (d[i] == INT_MAX) {
            out<<0<<" ";
        }
        else out<<d[i]<<" ";
    }

    in.close();
    out.close();
    return 0;
}