#include <bits/stdc++.h>
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define INF 1e9
#define MAXN 50005

using namespace std;

//vector< int > V[MAXN];
//vector< int > C[MAXN];

vector< pair<int, int> > Graph[ MAXN ];

set<pair<int, int>> s;

int d[ MAXN ];

bool visited[ MAXN ];

void Dijkstra() {

     d[ 1 ] = 0;
    //       {cost, node}
     s.insert( {0, 1} );

     while( !s.empty() ) {

            set<pair<int, int>> :: iterator it = s.begin();

            int node = it->second;

            s.erase( it );

            if( visited[ node ] ) continue;

            visited[ node ] = 1;

            for(int i = 0; i < Graph[node].size(); ++i) {

                int x = Graph[ node ][ i ].second;

                int c = Graph[ node ][ i ].first;

                if(!visited[x] && d[node] + c < d[x]) {

                    d[x] = d[node] + c;

                    s.insert({d[x],x});
                }

            }
     }
}

int main(int argc, char const *argv[]) {

   int n, m, x, y, c;

   freopen(FIN, "r", stdin);

   scanf("%d %d", &n, &m);

   for(int i = 1; i <= n; ++i) d[i] = INF;

   /*
   5 6
   1 2 1
   1 4 2
   4 3 4
   2 3 2
   4 5 3
   3 5 6
   */

   for(int i = 1; i <= m; ++i) {

       scanf("%d %d %d", &x, &y, &c);

       Graph[ x ].push_back( {c, y} );
      /*
      5 6
      1 2 1
      1 4 2
      4 3 4
      2 3 2
      4 5 3
      3 5 6
      */
       //Graph[ 1 ].push_back( {2, 1} );
       //Graph[ 1 ].push_back( {4, 2} );
       //Graph[ 4 ].push_back( {3, 4} );
       //Graph[ 2 ].push_back( {3, 2} );
       //Graph[ 4 ].push_back( {5, 3} );
       //Graph[ 3 ].push_back( {5, 6} );

       //Graph[1]=({2, 1}, {4,2})
   }

   Dijkstra();

   freopen(FOUT, "w", stdout);

   for(int i = 2; i <= n; i++) cout<< (d[i] != INF ? d[ i ] : 0 ) << " ";

  return 0;
}