#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define inf 10000000000
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.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;
         }
         
          
       }
     }
   }
   
}

int 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++)
  {
    if (d[i] < inf) out << d[i] << ' ';
    out<<d[i]<<' ';
  }
  
  
  return 0;
}