#include <fstream>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int loc[50001],k,i,j,aa,b,d,n,m,pana[50001],tot,aprox[50001];
vector<int> V[50001],Vd[50001];
struct locuri
{
    int nri,val;
}a[50001];
void adauga(int ii, int nr)
{
  tot++; k=tot;
  a[k].val=nr; a[k].nri=ii; loc[ii]=k;
  while(k>0 and a[k].val<a[k/2].val)
  {
    swap(loc[ii],loc[a[k/2].nri]);
    swap(a[k],a[k/2]);
    k=k/2;
  }
}
int minim(int x,int y)
{
    if (x<y) return k*2; else return k*2+1;
}
void sterge(int nr)
{
    int mini;
   k=loc[nr];
   swap(loc[a[k].nri],loc[a[tot].nri]);
   a[k].val=a[tot].val; a[k].nri=a[tot].nri;
   tot--;
   while(2*k<=tot)
  {
    mini=minim(a[k*2].val,a[k*2+1].val);
    swap(loc[a[k].nri],loc[a[mini].nri]);
    swap(a[k],a[mini]);
    k=mini;
  }
}

void init()
{
    for (i=2;i<=n;i++)
         {pana[i]=1000*50000+1; adauga(i,1000*50000+1);}
    adauga(1,0);
}
void portocala()
{  int nod,x;
    while (tot)
    {
        nod=a[1].nri;
        sterge(nod);
        for (size_t i = 0; i<V[nod].size(); i++)
        {
         x = pana[nod] + Vd[nod][i];
         if (x < pana[V[nod][i]])
         {
             pana[V[nod][i]] = x;
             aprox[V[nod][i]] = nod;
             sterge(V[nod][i]); adauga(V[nod][i],x);
         }
        }
    }
}
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>aa>>b>>d;
        V[aa].push_back(b);
        Vd[aa].push_back(d);
    }
    init();
    portocala();
    for (i=2;i<=n;i++)
    if (pana[i]!=50000*1000+1) g<<pana[i]<<" "; else g<<0<<" ";
    return 0;
}