#include<stdio.h>
#include<vector>
#include<queue>
#define nmax 50002
#define mult 99999999
using namespace std;


void solve();
void end_the_show();

int d[nmax];

vector < pair<int,int> >graf[nmax];

bool q[nmax];

int N,M;
 
int main()
{
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 
 scanf("%d%d",&N,&M);   
    
 int i,aux1,aux2,aux3,aux4;   
    
 for(i=1; i<=M; ++i)
 scanf("%d%d%d",&aux1,&aux2,&aux3),   
 graf[aux1].push_back( make_pair(aux2,aux3));

 solve();
 
 return 0;
}
    
void solve()
{   
    int i,nod,aux1;
    queue<int> C;
   
    vector< pair<int,int> >::iterator it;
    vector< pair<int,int> >::iterator stuff;
    
    for(i=1; i<=N; ++i)
    d[i]=mult,q[i]=false;
    
    d[1]=0;
    C.push(1);
    q[1]=true;
  //  i=0;
    while( !C.empty() )
    {
           nod=C.front();
           q[nod]=false;
           
           
           stuff=graf[nod].end();
           
           for(it=graf[nod].begin(); it!=stuff; ++it)
          { 
               aux1=d[nod]+it->second;
           
               if( d[it->first] > aux1 ){
                   d[it->first]= aux1;
                   
                   if( !q[it->first] )
                   {
                       q[it->first]=true;
                       C.push(it->first);
                   }  
               }
             //  ++i;
          }
    
           C.pop();
    }

end_the_show();    

} 

void end_the_show()
{
     int i;
     for(i=2; i<=N; ++i){
     if( d[i]!=mult ){
     printf("%d ",d[i]);continue;}
     printf("0 ");
     }
     printf("\n");

}