#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

#define INFILE "dijkstra.in" 
#define OUTFILE "dijkstra.out"
#define pb push_back
#define pii pair<int,int>
#define NMAX 50010

vector< vector< pii > > e(NMAX);
int n,m, dist[NMAX];
priority_queue<pii, vector<pii >, greater<pii > > q;
const int inf = 1000000000;

void dijkstra(int start) {
   for(int i=0; i<n; i++)
      dist[i] = inf;

   q.push(make_pair(start, 0));
   while( !q.empty() )
   {
      pii nod = q.top(); 
      q.pop();
      // first = vecin, second = cost
      int x = nod.first;
      int c = nod.second;
      if( dist[x]<inf ) continue;
      dist[x] = c;
      for(vector<pii >::iterator it=e[x].begin(); it!=e[x].end(); it++)
         if( dist[ it->first ]==inf )
            q.push(make_pair(it->first, it->second + c));
   }
}

int main() {
   freopen(INFILE, "r", stdin);
   freopen(OUTFILE, "w", stdout);

   cin >> n >> m;
   for(int i=0; i<m; i++) {
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      a--; b--;
      e[a].pb(make_pair(b, c));
   }

   dijkstra(0);
   for(int i=1; i<n; i++)
      printf("%d ", dist[i]);

   return 0;
}