#include <fstream>
#include <algorithm>
#include <vector>
#define inf 1<<30
#define maxn 50010

using namespace std;
int k,n,m;
vector<pair<int,int> > a[maxn];
int poz[maxn],h[maxn],d[maxn];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void read()
{
    in>>n>>m;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }

}
int left_son(int i)
{
    return 2*i;
}

int right_son(int i)
{
    return 2*i+1;
}

void up(int nod)
{
    while(nod/2!=0 && d[h[nod/2]]>d[h[nod]])
    {
        swap(poz[h[nod]],poz[h[nod/2]]);
        swap(h[nod],h[nod/2]);
        nod/=2;
    }
}

void down(int nod)
{
    int son=0;
    do
    {
        son=0;
        if(left_son(nod)<=k)
          son=left_son(nod);

        if(right_son(nod)<=k && d[h[left_son(nod)]]>d[h[right_son(nod)]])
        son=right_son(nod);

      if(d[h[son]]>d[h[nod]]) son=0;
      if(son)
      {
          swap(poz[h[son]],poz[h[nod]]);
          swap(h[nod],h[son]);

          nod=son;
      }
    }while(son);
}

void dijkstra()
{
    for(int i=1;i<=n;i++)
     d[i]=inf,poz[i]=-1;
     d[1]=0;
     poz[1]=1,k=1;
     h[1]=1;

     while(k)
     {
         int mini=h[1];
         h[1]=h[k];
         poz[h[1]]=1;
         k--;
         down(1);
         int nod=mini;

         for(int i=0;i<a[nod].size();i++)
         {
             int nodc=a[nod][i].first;
             int costc=a[nod][i].second;
             if(d[nodc]>d[nod]+costc)
             {
                 d[nodc]=d[nod]+costc;
                 if(poz[nodc]==-1)
                 {
                     k+=1;
                     poz[nodc]=k;
                     h[k]=nodc;
                     up(k);
                 }
                 else up(poz[nodc]);
             }
         }
     }
}
int main()
{
    read();
    dijkstra();
    for(int i=2;i<=n;i++)
    if(d[i]==inf) out<<"0 ";else
    out<<d[i]<<" ";
    return 0;
}