#include <fstream>
#define nmax 50000
#define INF 50000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int U[nmax], D[nmax], C[20000][20000], N, M;

void dijkstra()
{
     int min, nod, i;
     D[1] = 1;
     for(i=2; i<=N; ++i) D[i] = INF;
     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()
{
    int i, j, x, y, c;
    f >> N >> M;
    for(i=1; i<=N; ++i)
       for(j=1; j<=M; ++j)
          C[i][j] = INF;
    for(; M>0; --M)
    {
          f >> x >> y >> c;
          C[x][y] = c;
    }
    dijkstra();
    for(i=2; i<=N; ++i)
        g << D[i]-1 << " ";
    return 0;
}