#include <vector>
#include <cstdio>

using namespace std;

#define MAXN 50005
const int INF=1<<30;

struct nod{
  int nod,cost;
};

vector <nod> lista[MAXN];
int dist[MAXN];
int heap[MAXN],k;//k este nr de noduri din heap
int poz[MAXN];//0 daca nu e in heap , indicele locului in heap daca este deja in heap

void urca(int loc){
   int x;
   int aux;
   while((x=loc>>1) && dist[heap[loc]]<dist[heap[x]]){
      //interschimb nodul de pe locul loc cu tatal sau
      poz[heap[x]]=loc;
      poz[heap[loc]]=x;
      aux=heap[loc];
      heap[loc]=heap[x];
      heap[x]=aux;
      loc=x;
   }
}

void coboara(int loc){
   //cobor in fiul cel mai mic dintre cei doi
    int aux, x, y = 0;
    while (loc != y){
	y = loc;
	if ((x=y<<1)<=k && dist[heap[loc]]>dist[heap[x]]) loc = x;
        x++;
	if (x<=k && dist[heap[loc]]>dist[heap[x]]) loc = x;
          aux = heap[loc];
	  heap[loc] = heap[y];
	  heap[y] = aux;
          poz[heap[loc]] = loc;
	  poz[heap[y]] = y;
	}
}

int main(){
  FILE *fin=fopen("dijkstra.in","r");
  FILE *fout=fopen("dijkstra.out","w");
  int N,M,a,b,c;
  fscanf(fin,"%d%d",&N,&M);
  int i;
  nod aux;
  for(i=0;i<M;i++){
     fscanf(fin,"%d%d%d",&a,&b,&c);
     aux.nod=b;
     aux.cost=c;
     lista[a].push_back(aux);
  }
  //final citire
  //initializari
    for(i=2;i<=N;i++){
      dist[i]=INF;
      //poz[i]=-1;//nu sunt in heap
    
    }
    dist[1]=0;
    poz[1]=1;
  k=1;//cate noduri sunt in heap
    //adaug sursa in heap
    heap[1]=1;
  int min,aux1,aux2;
    while(k){//cat timp heapul nu e vid
       min=heap[1];//e min-heap; tine doar noduri nevizitate in el
      //scot varful heapului....
       heap[1]=heap[k];
       poz[heap[1]]=1;
       k--;
       coboara(1);
       //heap tine indicii nodurilor 
       for(i=0;i<lista[min].size();i++){
           //daca valoarea nodului lista[min][i] se poate imbunatati prin nodul min
           aux1=lista[min][i].nod;
           aux2=lista[min][i].cost;
           if(dist[aux1]>dist[min]+aux2){
                 dist[aux1]=dist[min]+aux2;
                 //am imbunatatit val nodului lista[min][i]
                 if(poz[aux1]){
                    //e deja in heap, doar ca acum are alta valoare, mai mica
                    //trebuie urcat in heap
                    urca(poz[aux1]);
                 }else{
                    //nu e in heap, trebuie adaugat
                    heap[++k]=aux1;
                    poz[heap[k]]=k;
                    urca(k);
                 }
           }
       }
    }
    for(i=2;i<=N;i++){
       fprintf(fout,"%d ",(dist[i]==INF?0:dist[i]));
    }
  fprintf(fout,"\n");

return 0;
}