#include<iostream>
#include<fstream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define MAX_N 10000
#define INF 0x3f3f
int N,M,i,C[MAX_N][MAX_N],D[MAX_N],T[MAX_N];
char U[MAX_N];

void dijkstra(int sursa)
{
     int i,min,nod;
     memset(U,0,sizeof(U));
     memset(T,0,sizeof(T));
     memset(D,63,sizeof(D));
     D[sursa]=0;
     while(1)
     {
          min=INF;
          nod=-1;
          for(i=1;i<=N;i++)
               if(!U[i] && min>D[i]) min=D[i], nod=i;
          if(min==INF) break;
          U[nod]=1;
          for(i=1;i<=N;i++)
               if(D[i]>D[nod]+C[nod][i]) D[i]=D[nod]+C[nod][i], T[i]=nod;
     }
}

int main ()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>N>>M;
    int j,c;
     for(i=1;i<=N;i++)
          for(j=1;j<=M;j++) C[i][j] = (i!=j)*INF;
     for(;M>0;M--)
     {
          f>>i>>j>>c;
          C[i][j]=c;
     }
    dijkstra(1);
    for(i=2;i<=N;i++) g<<D[i]<<" ";

     f.close(); g.close();
     return 0;
}