#include <fstream>
#define inf 20000000
#include<vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector< pair <int,int> > G[50001];
int n,m,i,j,d[50001],h[50001],poz[50001],dim,x,y,c,viz[50001],k,nod,cost,Min,aux;

void down(){
int k=1,st,dr,p=1,p1;
while(2*k<=dim){
    st=2*k;dr=2*k+1;p=k;
    if(d[h[st]]<d[h[k]]){
        p=st;
    }
    if(dr<=dim&&d[h[dr]]<d[h[p]])
        p=dr;
    if(p!=k){
        swap(h[p],h[k]);
        poz[h[p]]=p;
        poz[h[k]]=k;
        k=p;
    }
  else break;
}
}

void up(int p){
 while(p/2>=1){
    if(d[h[p/2]]>d[h[p]])
         {
           int  aux=h[p/2];
             h[p/2]=h[p];
             poz[h[p/2]]=p/2;
             h[p]=aux;
             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;
    h[1]=1;dim=1;poz[1]=1;
    for(i=2;i<=n;i++)
         d[i]=inf;
    for(int j=1;j<=n;j++){
        k=h[1];viz[k]=1;
        aux=h[1];
        h[1]=h[dim];
        poz[h[1]]=1;
       // poz[dim]=aux;
        dim--;
        down();
        for(i=0;i<G[k].size();i++){
                nod=G[k][i].first;
                 cost=G[k][i].second;Min=inf;
             if(viz[nod]==0)
                 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;
}