#include <fstream>
#include <vector>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,i,nod,x,pana[50001],aprox[50001],k,loc[50001],tot;
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(1,0);
}
void portocala()
{
    while (tot>0)
    {
        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]])
         {
             if (pana[V[nod][i]]!=50000*1000+1) sterge(V[nod][i]);
             pana[V[nod][i]] = x;
             aprox[V[nod][i]] = nod;
             adauga(V[nod][i],x);
         }
        }
    }
}
int main()
{
    int a,b,d,i,m;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>a>>b>>d;
        V[a].push_back(b);
        Vd[a].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;
}