//algoritmul Dijkstra - cu heap
#include<fstream>
#include<iostream>
using namespace std;

const int maxNrNoduri=50001,INF=2147483647;
 
struct Muchie{
    int nod,cost;
    Muchie *next;
};
 
int nrNoduri,nrMuchii;
Muchie *muchie[maxNrNoduri];
int cost[maxNrNoduri],poz[maxNrNoduri];

int heap[maxNrNoduri],dimHeap;

void add(int unde,int nod,int cost){
    Muchie *m=new Muchie;
    m->nod=nod;
    m->cost=cost;
    m->next=muchie[unde];
    muchie[unde]=m;
}
 
void schimba(int x,int y){
    int aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;
}
 
void urca(int nod){
    int tata;
    while (nod > 1){
        tata=nod>>1;
        if (cost[heap[tata]] > cost[heap[nod]]){
            poz[heap[nod]]=tata;
            poz[heap[tata]]=nod;
            schimba(tata,nod);
            nod=tata;
        }
        else
            nod=1;
    }
}
 
void coboara(int nod){
    int f;
    while (nod <= dimHeap){
        f=nod;
        if ((nod<<1) <= dimHeap){
            f=nod << 1;
            if (f+1 <= dimHeap)
                if (cost[heap[f + 1]] < cost[heap[f]])
                    ++f;
        }
        else	return;
        if (cost[heap[nod]] > cost[heap[f]]){
            poz[heap[nod]]=f;
            poz[heap[f]]=nod;
            schimba(nod,f);
            nod=f;
        }
        else	return;
    }
}
 
void Dijkstra(){
    for (int i=2; i <= nrNoduri; ++i)
        cost[i]=INF,poz[i]=-1;
    poz[1]=1;
    heap[++dimHeap]=1;
    while (dimHeap){
        int min=heap[1];
        schimba(1,dimHeap);
        poz[heap[1]]=1;
        --dimHeap;
        coboara(1);
		for(Muchie *m=muchie[min]; m; m=m->next)
            if (cost[m->nod] > cost[min] + m->cost){
                cost[m->nod]=cost[min] + m->cost;
                if (poz[m->nod] != -1)
                    urca(poz[m->nod]);
                else{
                    heap[++dimHeap]=m->nod;
                    poz[heap[dimHeap]]=dimHeap;
                    urca(dimHeap);
                }
            }
    }
}

void citire(){
	ifstream in("dijkstra.in");
	in>>nrNoduri>>nrMuchii;
    int x,y,c;
    for (int i=1; i <= nrMuchii; ++i){
		in>>x>>y>>c;
        add(x,y,c);
    }
}

void afisare(){
	ofstream out("dijkstra.out");
	for (int i=2; i <= nrNoduri; ++i)
		out<<(cost[i]==INF ? 0 :cost[i])<<" "; 
    out<<"\n";
}

int main(){
    citire();
    Dijkstra();
    afisare();
    return 0;
}