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

using namespace std;

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

int n,m, h[100002],nr,d[100002],poz[100002];
const int inf = 1 << 30;
struct el{
    int csucs,ar;
    struct el *kov;
}*L[100002],*q;

void add_to_list(int hova, int mit, int mennyit){
    q = new el;
    q -> csucs = mit;
    q -> ar = mennyit;
    q -> kov = L[hova];
    L[hova] = q;
}

void olvas(){
    int i,x,y,z;
    be >> n >> m;
    for(i = 1; i <= m; ++i){
        be >> x >> y >> z;
        add_to_list(x,y,z);
    }
}

void add_to_heap(int x){
    int i,aux;
    i = x;
    while(i > 1){
        if(d[h[i/2]] > d[h[i]]){
            poz[h[i]] = i/2;
            poz[h[i/2]] = i;
            aux = h[i/2]; h[i/2] = h[i]; h[i] = aux;
            i = i/2;
        }
        else i = 1;
    }
}

void delete_from_heap(){
    int i,j,aux;
    poz[h[1]] = nr; poz[h[nr]] = 1;
    aux = h[1]; h[1] = h[nr]; h[nr] = aux;
    nr = nr - 1;
    i = 1;
    while(i <= nr){
        if(2*i <= nr){
            j = 2*i;//the left
            if(j + 1 <= nr)//if the right exists
                if(d[h[j]] > d[h[j+1]]) j = j + 1;//and it is smaller get the smaller

            if(d[h[i]] > d[h[j]]){
                poz[h[i]] = j; poz[h[j]] = i;
                aux = h[i]; h[i] = h[j]; h[j] = aux;
                i = j;
            }
            else i = nr + 1;
        }
        else i = nr + 1;
    }
}

void dijkstra(int st){
    int i,nmin;
    //initialization of d
    for(i = 1; i <=n; i++) d[i] = inf;
    d[st] = 0;

    //create a heap with all nodes which can be reached from st
    q = L[st];//list number st
    while(q != NULL){
        d[q -> csucs] = q -> ar; //distance from st to q -> csucs
        nr = nr + 1;//increment elements in heap
        h[nr] = q -> csucs;//add node at the end of the heap
        poz[q -> csucs] = nr;//position of the new nod
        add_to_heap(nr);//actualize heap
        q = q -> kov;
    }

    while(nr > 0){//while heap is not empty
        nmin = h[1];//top of the heap is the node with minimum distance
        poz[h[1]] = 0;//it is no more in heap
        delete_from_heap();//delete this node from heap

        q = L[nmin];
        while(q != NULL){
            if(d[q -> csucs] > d[nmin] + q -> ar){
                d[q -> csucs] = d[nmin] + q -> ar;//relax
                //actualize the heap
                if(poz[q -> csucs] == 0){//node is not in the heap
                    nr = nr + 1;//add new node to heap
                    h[nr] = q -> csucs;
                    poz[q -> csucs] = nr;
                    add_to_heap(nr);//actualize heap
                }
                else {//node is already in heap
                    add_to_heap(poz[q -> csucs]);//just actualize the heap
                }
            }
            q = q -> kov;
        }
    }
    for(i = 1; i <= n; i++){
        if(i != st){
            if(d[i] == inf) ki << "0 ";
            else ki << d[i] << " ";
        }
    }
}

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