#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 2147000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> v[50005],c[50005];

int n,m,cmin[50005],use[50005];
struct elem
{ int x,cost; } el;
struct comp
{
  bool operator() (elem a,elem b)
  { return a.cost<b.cost;

  }
};

priority_queue <elem,vector<elem>,comp> heap;

void Dijk()
{ int i,nod,nod2;
    for(i=2;i<=n;i++)
     cmin[i]=inf;

   el.x=1; el.cost=0;
   use[1]=1;
  heap.push(el);
  while(!heap.empty())
  { el=heap.top(); heap.pop();

      if (el.cost==cmin[el.x])
      { nod=el.x; use[el.x]=1;
         for(i=0;i<v[nod].size();i++)
          if (!use[v[nod][i]])
          { nod2=v[nod][i];
             if (cmin[nod]+c[nod][i]<cmin[nod2])
             { cmin[nod2]=cmin[nod]+c[nod][i];
               el.x=nod2; el.cost=cmin[nod2];
               heap.push(el);
             }
          }
      }
  }
}
int main()
{ int i,x,y,cost;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>cost;
       v[x].push_back(y);
       c[x].push_back(cost);
    }
   Dijk();

   for(i=2;i<=n;i++)
    if (cmin[i]==inf) g<<"0 ";
     else g<<cmin[i]<<" ";

    return 0;
}