#include<fstream>
using namespace std;
typedef struct celula {
          int nod,cost;
          celula *next;
          }*lista;
typedef struct { int nod, cost; } tip;
lista graf[50005],v;
tip heap[150000];
int i,n,drum[50005],x,y,c,hp,m;
bool viz[50005];

void baga(int nod, int cost) {
     ++hp;
     heap[hp].nod=nod;
     heap[hp].cost=cost;
     int aux=hp;
     while (aux>1&&heap[aux/2].cost>heap[aux].cost) {
             swap(heap[aux/2],heap[aux]);
             aux/=2;
             }
}

void sterge() {
     heap[1]=heap[hp];
     --hp;
     int aux=1;
     while (2*aux<=hp) {
           
           int ind=aux;
           if (heap[2*aux].cost<heap[ind].cost) ind=2*aux;
           if (2*aux+1<=hp&&heap[2*aux+1].cost<heap[ind].cost) ind=2*aux+1;
           
           if (ind==aux) break;
            else { swap(heap[ind],heap[aux]); aux=ind; }
           }
}

int main(void) {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for (i=1; i<=m; ++i) {
        fin>>x>>y>>c;
        v=new celula; v->nod=y; v->cost=c; v->next=graf[x]; graf[x]=v;
        }
    
    baga(1,0);
    while (hp) {
           int nodc=heap[1].nod;
           sterge();
           if (viz[nodc]==0) {
            viz[nodc]=1;
             for (lista p=graf[nodc]; p; p=p->next) 
              if (drum[p->nod]==0||drum[p->nod]>drum[nodc]+p->cost) {
                drum[p->nod]=drum[nodc]+p->cost;
                  baga(p->nod,drum[p->nod]);
                  }
               }
           }
            
    
    for (i=2; i<=n; ++i) fout<<drum[i]<<" ";
 return(0);
}