#include<fstream>
#include<vector>
#define maxn 50004
#define inf 123456789
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

struct pereche{
       int dist;
       int nod;
       };

vector < pair <int,int> > a[maxn];
int i,n,m,x,y,cost,d[maxn];
pereche h[maxn];
int heap_size;
int nod;

void swap(pereche &a,pereche &b){
     pereche aux;
     aux=a; a=b; b=aux;
}

void down_heap(int heap_size,int k){
     int son=1;
     
     while(son)
     {
      son=0;
      if(2*k<=heap_size){
                         son=2*k;
                         if(2*k+1<=heap_size && h[2*k+1].dist<h[2*k].dist) 
                           son=2*k+1;
                         
                         if(h[son].dist<h[k].dist){
                                                   swap(h[son],h[k]);
                                                   k=son;
                                                  }
                         else son=0;
                        }
     }
}

void up_heap(int heap_size,int k){
     int distanta=h[k].dist;
     int nr_nod=h[k].nod;
     
     while(k>1 && distanta<h[k/2].dist){
                                        h[k]=h[k/2];
                                        k=k/2;
                                       }
     h[k].dist=distanta;
     h[k].nod=nr_nod;
}

void insert_heap(int &heap_size,int distanta,int nr_nod){
     heap_size++;
     h[heap_size].dist=distanta;
     h[heap_size].nod=nr_nod;
     
     up_heap(heap_size,heap_size);
}

void delete_heap(int &heap_size,int k){
     h[k]=h[heap_size];
     heap_size--;
     
     if(k>1 && h[k].dist<h[k/2].dist) up_heap(heap_size,k);
     else down_heap(heap_size,k);
}

int main(){
    fi>>n>>m;
    for(i=1;i<=m;i++){
                      fi>>x>>y>>cost;
                      a[x].push_back(make_pair(y,cost));
                     }
    
    for(i=1;i<=n;i++) d[i]=inf;
    d[1]=0;
    
    h[1].dist=d[1];
    h[1].nod=1;
    heap_size=1;
    
    while(heap_size){
                     nod=h[1].nod;
                     delete_heap(heap_size,1);
                     
                     for(i=0;i<(int)a[nod].size();i++)
                         {
                          x=nod;
                          y=a[nod][i].first;
                          cost=a[nod][i].second;
                          
                          if(d[x]+cost<d[y]){
                                             d[y]=d[x]+cost;
                                             insert_heap(heap_size,d[y],y);
                                            }
                         }
                    }
    
    for(i=2;i<=n;i++) 
      if(d[i]!=inf) fo<<d[i]<<" ";
      else fo<<"0 ";
    
    fi.close();
    fo.close();
    return 0;
}