#include <stdio.h>
#include <vector>
#include <set>
#include <list>
using namespace std;

#define inf 2000000

struct nod_g{
    int nod, cost;
};


vector < list<nod_g> > graf;
list <nod_g>::iterator it, last;
vector <bool> vizitat;
vector <int> cost;

struct compare{
    bool operator() (int i, int j){
        return cost[i] > cost[j];
    }
};

set <int, compare> heap;
int n, m;

void citire(){
    freopen("dijkstra.in", "r", stdin);
    int x, y, c;
    nod_g aux;
    fscanf(stdin, "%i %i", &n, &m);

    graf.resize(n+1);
    vizitat.resize(n+1);
    cost.resize(n+1, inf);

    for(int i = 1; i <= m; ++i){
        fscanf(stdin, "%i %i %i", &x, &y, &c);
        aux.nod = y; aux.cost = c;
        graf[x].push_back(aux);
    }
    fclose(stdin);
}

void dijkstra(){
    int first = 1, nod, costt;
    heap.insert(1);
    cost[1] = 0;

    while(!heap.empty()){
        first = *heap.begin();
        heap.erase(heap.begin());

        it = graf[first].begin();
        last = graf[first].end();

        if(!vizitat[first]){
            for(; it != last; ++it){
                nod = it->nod; costt = it->cost;

                if(cost[nod] > cost[first] + costt){
                    cost[nod] = cost[first] + costt;
                    if(!vizitat[nod]) heap.insert(nod);
                }
            }
        }
    }
}

void afis(){
    for(int i = 2; i <= n; ++i)
        fprintf(stdout, "%i ", (cost[i] != inf) ? cost[i] : 0 );
    fclose(stdout);
}

void afisgraf(){
    for(int i = 1; i <= n; ++i, fprintf(stdout, "\n"))
        for(it = graf[i].begin(); it != graf[i].end(); ++it)
            fprintf(stdout, "%i ", it->nod);
}

int main(){
    freopen("dijkstra.out", "w", stdout);
    citire();
    dijkstra();
    afis();
    fclose(stdout);

    return 0;
}