#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int nodes = 50003;
int n, m;
int howmany;
int heap[nodes];
int p[nodes];
vector <int> d(nodes, 0x3f3f3f);
vector < pair <int, int> > v[nodes];


// heap[i ] : al i-lea element din heap
// p [ i ] : pozitia lui i in heap


void change (int x, int y){
    swap(p[heap[x]], p[heap[y]]);
    swap(heap[x], heap[y]);
}

void urca (int who){
    while (who >> 1){
            int father = who >> 1;
            if (d[heap[who]] > d[heap[father]])
                change(who, father);
            else return ;
            who = father ;
    }
}

void push (int who){
    heap[++howmany] = who;
    p[ who ] = howmany;
    urca(who);
}

void downit (int who){
    int son = who << 1; // Alegem fiul de valoare minima
    if (d[heap[son + 1]] < d[heap[son]] && son + 1 <= howmany)
        son++;
    if (son <= howmany){
            change(son, who);
            downit(son);
    }
}

void Remove (int who){
    change(who ,howmany);
    p[heap[howmany] ] = 0;
    heap[howmany -- ] = 0;
    downit(who );
}

void dijkstra ( ) {
    d[1 ] = 0;
    push(1 );
    while (howmany) {
            int now = heap[1];
            for (const auto &it : v[now]){
                    int where = it.first;
                    if (d[where] > d[now] + it.second){
                            d[where] = d[now] + it.second;
                            if (p[where ])
                                urca(p [ where ]); // s-a schimbat dist, era in heap
                            else push(where) ;
                    }
            }
            Remove(1);
    }
}


int main(){
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
            int x, y, cost;
            fin >> x >> y >> cost;
            v[x].push_back({y, cost});
    }
    dijkstra();
    for (int i = 2; i <= n; i++)
        fout << (d[i] != 0x3f3f3f ? d[i] : 0) << " ";
}