#include <fstream>
#include <vector>
#include <queue>
#define mp make_pair
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector < pair < int, int> > G[50001];
int D[50001],n,m,i,x,y,c,Q[50001],st,dr;

void Djikstra (int nod)
{
   int it;
   st=dr=1;
   Q[1]=1;

   while (st<=dr)
   {
       nod=Q[st];
       for (i=0; i<G[nod].size(); i++)
         if (D[nod]+G[nod][i].second<D[G[nod][i].first])
           D[G[nod][i].first]=D[nod]+G[nod][i].second,
           Q[++dr]=G[nod][i].first;
       st++;
    }
}

int main ()
{
  f>>n>>m;
  for (i=1;i<=m;i++)
  {
      f>>x>>y>>c;
      G[x].push_back(mp(y,c));
  }

for (i=1;i<=n;i++) D[i]=INF;
D[1]=0;

Djikstra(1);

for (i=2;i<=n;i++) g<<D[i]<<' ';

return 0;
}