#include <vector>
#include <list>
#include <queue>
#include <fstream>
#include <utility>
#include <functional>
using namespace std;

const int INF = 2000000000;

typedef pair <int, int> pii;
typedef list <pii>::iterator l_it;

int n;
vector <list <pii> > muchii;
vector <int> minim;
priority_queue <pii, vector <pii>, greater <pii> > heap;

int main(void) {
    ifstream fin("dijkstra.in"); int m, n1, n2, c;
    fin >> n >> m;
    muchii.resize(n);
    for(int i = 0; i < m; ++i) {
        fin >> n1 >> n2 >> c;
        muchii[n1-1].push_back(make_pair(n2-1, c));
    }
    fin.close();
    
    minim.resize(n, INF);
    minim[0] = 0; heap.push(make_pair(0, 0));
    while(!heap.empty()) {
        int varf = heap.top().second; heap.pop();
        for(l_it it = muchii[varf].begin(); it != muchii[varf].end(); ++it)
            if(minim[varf] + it->second < minim[it->first]) {
                minim[it->first] = minim[varf] + it->second;
                heap.push(make_pair(minim[varf] + it->second, it->first));
            }
    }
    
    ofstream fout("dijkstra.out");
    for(int i = 1; i < n; ++i)
        fout << (minim[i] == INF ? 0 : minim[i]) << ' ';
    fout.close();
}