#include<fstream>
#include<cstring>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int NM = 50005;
const int MM = 250005;

typedef struct lnod{
          int vf,cost;
          struct lnod *next;
          }*Nod;
          
Nod a[NM];
int N,M;
int D[NM];
bool viz[NM];
queue<int> Q;

void add(int x,int y,int c){
     Nod p = new lnod;
     p->vf=y;
     p->cost=c;
     p->next=a[x];
     a[x]=p;   
}

void readdata(){
    ifstream fin("dijkstra.in");
    int i,a,b,c;
    fin>>N>>M;
    for(i=1;i<=M;++i){
          fin>>a>>b>>c; 
          add(a,b,c);
          }     
     }

void Bellman_Ford(){
     int nod;
     memset(D,INF,sizeof(D));
     D[1]=0;
     Q.push(1);
     viz[1]=1;
     
     while(!Q.empty())
      {
              nod = Q.front();
              Q.pop();
              viz[nod] = 0;
              
              for(Nod p=a[nod];p;p=p->next)
                if(D[nod] + p->cost < D[p->vf])
                {
                 D[p->vf] = D[nod] + p->cost;
                 if(!viz[p->vf])
                   {
                    Q.push(p->vf);
                    viz[p->vf]=1;
                   }           
                }                                                                                        
      }
}        

void writedata(){
    ofstream fout("dijkstra.out");
    for(int i=2;i<=N;++i)
      fout<<(D[i]!=INF?D[i]:0)<<' ';     
}           

int main(void){
    readdata();    
    Bellman_Ford();
    writedata();
 return 0;   
}