#include<fstream>
#include<stdlib.h>
#define nmax 50020
#define oo 10000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int i,j , *A[nmax], d[nmax], mini, i0, s[nmax], n, m  ;
int *B[nmax];
int x,y,dis;
int dijkstra(int r)
{
    int i;
    for(i = 1; i <= n ;i++)
        d[i] = 0;
    for(i = 1; i <= A[r][0]; ++i)
        d[A[r][i]] = B[r][i];
    //for(i = 1 ; i<= n ;i++){
       // if(d[i] == -1)
          //  d[i] =oo;
       // fout << d[i] <<" ";

    for(int k = 1; k < n ;k++)
    {
        mini = oo;
        for(i = 1; i <= n; i++)
        {
            if(s[i] == 0 && d[i] <mini && d[i] )
            {
                i0 = i;
                mini =d[i];
            }
        }
        s[i0] = 1;
       // fout <<'\n' ;
        //fout << mini <<" " <<i0 <<" " ;
        for(i = 1; i <= A[i0][0];i++)
        {
           // fout <<B[i0][i] <<" " ;
            if(mini + B[i0][i]< d[A[i0][i]] || d[A[i0][i]]==0 )
                d[A[i0][i]] = mini + B[i0][i];
        }
    }

    for(i = 2; i <= n ;i++)
        fout <<d[i] <<" " ;

}
void read()
{
    int i;
    fin >> n >> m;
    for(i = 1; i <= n ;i++)
    {
        A[i] = (int *) realloc(A[i], sizeof(int));
        A[i][0]= 0 ;
    }
    for(i = 1; i <= m ;i++)
    {
        fin >>x >> y >>dis;
        A[x][0]++;

        A[x] = (int *) realloc(A[x], sizeof(int) * (A[x][0] + 1));
        B[x] =(int *) realloc(B[x], sizeof(int) * (A[x][0] + 1));
        A[x][A[x][0]] = y;
        B[x][A[x][0]] = dis;
      //  fout << x <<A[x][A[x][0]] <<'\n' ;
    }
    dijkstra(1);
}
int main()
{
    read();
    fin.close();
    return 0;;

}