#include <fstream>
#include<vector>
#define inf 200000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector< pair <int,int> >G[50001];
int d[50001],h[50001],poz[50001],n,m,i,viz[50001],x,y,c,dim;
void down(){
   int k=1,st,dr,p;
   while(2*k<=dim){
        st=2*k;dr=st+1;p=k;
       if(d[h[p]]>d[h[st]])
             p=st;
       if(dr<=dim&&d[h[p]]>d[h[dr]])
          p=dr;
      if(k!=p){
        swap(h[k],h[p]);
        poz[h[k]]=k;
        poz[h[p]]=p;
        k=p;
      }
     else
        break;
   }
}
void up(int p){

  while(p/2>=1){
    if(d[h[p/2]]>d[h[p]])
       {
           swap(h[p/2],h[p]);
           poz[h[p/2]]=p/2;
           poz[h[p]]=p;
           p=p/2;
       }
      else
        break;

  }

}
int main()
{
    f>>n>>m;
for(i=1;i<=m;i++)
{
    f>>x>>y>>c;
    G[x].push_back(make_pair(y,c));
}
d[1]=0;
for(i=2;i<=n;i++)
    d[i]=inf;
h[1]=1;poz[1]=1;dim=1;
for(i=1;i<=n;i++){
   int k=h[1];
       h[1]=h[dim];
       poz[h[1]]=1;
       dim--;
       down();
       viz[k]=1;
      for(int i=0;i<G[k].size();++i)
      {
          int nod=G[k][i].first;
          int cost=G[k][i].second;
          if(d[nod]>d[k]+cost){
             d[nod]=d[k]+cost;
             if(poz[nod]==0){
                dim++;
                h[dim]=nod;
                poz[nod]=dim;
                up(dim);
             }
             else
                up(poz[nod]);

          }
      }


}
for(i=2;i<=n;i++)
    if(d[i]!=inf)
       g<<d[i]<<" ";
  else
    g<<0<<" ";
    return 0;
}