#include <iostream>
#include <fstream>
#define INF 5000000002;

using namespace std;

ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");

int n,m,csmin;
struct lista{
    int csucs,ar;
    struct lista *next;
};
struct lista *a[50002], *elem;

long long d[50002],vmin;
bool viz[50002];

void olvas(){
    int i,x,y,z;
    be >> n >> m;
   /* for(i = 1; i<=n; ++i){
        a[i] = new lista;
        a[i]->next = NULL;
    }*/
    for(i = 1; i <= m; ++i){
        be >> x >> y >> z;
        elem = new lista;
        elem->csucs = y;
        elem->ar = z;
        elem->next = a[x];
        a[x] = elem;

    }
/*
    for(i = 1; i <= n; ++i){
        ki << i << ":";
        elem = a[i]->next;
        while(elem != NULL){
            ki << elem->csucs << " ";
            elem=elem->next;
        }
        ki << "\n";
    }*/
}
void dijkstra(){
    int i,j;
    for(i = 1; i <= n; ++i) {
            d[i] = INF;
            viz[i] = false;
    }
    d[1] = 0;
    elem = a[1];
    while(elem != NULL){
        d[elem->csucs] = elem->ar;
        elem = elem->next;
    }
    viz[1] = true;
    for(i = 2; i <=n; i++){
        vmin = INF;
        csmin = 0;
        for(j = 2; j <= n; j++){
            if(viz[j] == false && d[j] < vmin) {
                vmin = d[j];
                csmin = j;
            }
        }
        viz[csmin] = true;

        elem = a[csmin];
        while(elem != NULL){
            if(viz[elem->csucs] == false){
                if(d[elem->csucs] > d[csmin] + elem->ar)
                    d[elem->csucs] = d[csmin] + elem->ar;
            }
            elem = elem->next;
        }
    }

    for(i = 2; i <= n; ++i) {
            if(d[i] == 5000000002) d[i] = 0;
            ki << d[i] << " ";
    }
}

int main()
{
    olvas();
    dijkstra();
    return 0;
}