#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;

set < pair<int, int> > 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 nod, costt;
    pair<int, int> first;
    heap.insert(make_pair(0, 1));
    cost[1] = 0;

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

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

        for(; it != last; ++it){
            nod = it->nod; costt = it->cost;

            if(cost[nod] > cost[first.second] + costt){
                cost[nod] = cost[first.second] + costt;
                heap.insert(make_pair(cost[nod], 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;
}