#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define inf 9223372036854775807
#define int long long

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

 struct vecin
 {
   int nod, cost;
 };

 vector <vecin>  a[50001];
 int N, M;
 queue <int> q;
 int inqueue[50001]; // ==0   nu este in coada

 long long d[50001];

 int cnt[50001];


void bellman(int x)
{
   q.push(x);
   d[x] = 0;
   inqueue[x] = 1;
   while(!q.empty())
   {
     int vf = q.front();
     q.pop();
     inqueue[vf] = 0;
     // vecinii lui vf
     int k = a[vf].size();
     // a[vf][0].....a[vf][k-1]
     for(int i = 0; i < k; i++)
     {
       if( d[ a[vf][i].nod ] > a[vf][i].cost + d[vf])
       {
         d[ a[vf][i].nod ] = a[vf][i].cost + d[vf];

         if(inqueue[  a[vf][i].nod   ] == 0)
         {
           q.push(a[vf][i].nod);
           cnt[a[vf][i].nod]++;
           inqueue[a[vf][i].nod ] = 1;
         }


       }
     }
   }

}

signed main()
{
  in >> N >> M;
  for (int i = 1; i <= M; i++)
  {
    int x, y, c;
    in >> x >> y >> c;
    a[x].push_back({y, c});
  }

  for(int i = 1; i <= N ; i++)
  {
    d[i] = inf;
  }
  for(int i = 1; i <= N ; i++)
  {
    inqueue[i] = 0;
  }
  for(int i = 1; i <= N ; i++)
  {
    cnt[i] = 0;
  }
  bellman(1);
  for(int i = 2; i <= N ; i++)
  {
    out<<d[i]<<' ';
  }


  return 0;
}