#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,H[50001],Poz[50001],nrh;

void Swap (int x, int y)
{
    int aux;
    aux=H[x], H[x]=H[y], H[y]=aux;
    aux=Poz[H[x]], Poz[H[x]]=Poz[H[y]], Poz[H[y]]=aux;
}

void HeapUp (int poz)
{
    if (D[H[poz]]<D[H[poz/2]] && poz/2>0)
    {
        Swap(poz,poz/2);
        HeapUp(poz/2);
    }
}

void Expand (int nod)
{
   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;
             HeapUp(G[nod][i].first);
         }
}

void HeapDown (int poz)
{
    int pz;

    if (H[poz*2]>H[poz*2+1] && poz*2+1<=nrh) pz=poz*2+1;
    else
    pz=poz*2;

    if (D[H[poz]]> D[H[pz]] && pz<=nrh)
    {
        Swap(poz, pz);
        HeapDown(pz);
    }
}

void Djikstra (int nod)
{
   nrh=n;

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

   while (nrh>=1)
   {
       Swap(1,nrh);
       nrh--;
       HeapDown(1);
       Expand(H[nrh+1]);

   }
}

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

Djikstra(1);

for (i=2;i<=n;i++) if (D[i]!=INF) g<<D[i]<<' '; else g<<"0 ";

return 0;
}