#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define NMAX 50005
#define inf 0x3f3f3f3f

using namespace std;

int n, m, best[NMAX];
vector<pair<int, int> > v[NMAX]; /// .second = cost
queue<pair<int, int> > q;

void read()
{
   int A, B, C;
   scanf("%d %d\n", &n, &m);
   for (int i=1; i<=m; i++){
      scanf("%d %d %d\n", &A, &B, &C);
      v[A].push_back(make_pair(B, C));
   }
}

void dijkstra()
{
   pair<int, int> nodC, nodV;
   vector<pair<int, int> >::iterator it;
   memset(best, inf, sizeof(best));
   best[1] = 0;
   q.push(make_pair(1, 0));
   while (!q.empty()){
      nodC = q.front();
      q.pop();
      for (it = v[nodC.first].begin(); it != v[nodC.first].end(); ++it){
         nodV = *it;
         if (best[nodV.first] > best[nodC.first] + nodV.second){
            best[nodV.first] = best[nodC.first] + nodV.second;
            q.push(make_pair(nodV.first, best[nodV.first]));
         }
      }
   }
}

void print()
{
   for (int i=2; i<=n; i++){
      if (best[i] == inf)
         printf("0 ");
      else
         printf("%d ", best[i]);
   }
}

int main()
{
   freopen("dijkstra.in", "r", stdin);
   freopen("dijkstra.out", "w", stdout);
   read();
   dijkstra();
   print();

   return 0;
}