#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

 struct muchie
 { int nod,cost; } ;

 struct cmp
 {
   bool operator() (muchie a,muchie b)
    { return a.cost>b.cost;}

 };
 vector <muchie> v[50005];

 muchie newm,el;

  int n,m,dm[50005],use[50005],inf=2147000000;

 priority_queue<muchie,vector<muchie>,cmp> heap;

int main()
{  int i,x,y,c;
  f>>n>>m;

  for(i=1;i<=m;i++)
  {
      f>>x>>newm.nod>>newm.cost;
       v[x].push_back(newm);
  }
   dm[1]=0;
    for(i=2;i<=n;i++)
     dm[i]=inf;
   newm.nod=1; newm.cost=0;
    heap.push(newm);

     while(!heap.empty())
     {
       newm=heap.top(); heap.pop();
         x=newm.nod;
          if (dm[x]==newm.cost)
            for(i=0;i<v[x].size();i++)
             if (newm.cost + v[x][i].cost < dm[v[x][i].nod])
              {  el.nod=v[x][i].nod;
                   el.cost=newm.cost+v[x][i].cost;
                   heap.push(el);
                  dm[v[x][i].nod]=newm.cost+v[x][i].cost;
              }

     }

      for(i=2;i<=n;i++)
       g<<(dm[i]==inf?0:dm[i])<<" ";
    return 0;
}