#include<fstream.h>
#define dim 50001
#define inf 10001
int n,m[dim],d[dim];
int (*c)[dim]=new int [dim][dim];
//int c[dim][dim];
ofstream g("dijkstra.out");
void initializare()
{int i,j,m2,x,y,cost;
 ifstream f("dijkstra.in");
 f>>n>>m2;
 for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
   c[j][i]=c[i][j]=inf;
 for(i=1;i<=m2;i++)
  {f>>x>>y>>cost;
   c[x][y]=cost;
  }
 for(i=1;i<=n;i++)
  d[i]=c[1][i];
 m[1]=1;
 f.close();
}
void afisare()
{int i;
 for(i=2;i<=n;i++)
  if(d[i]==inf) g<<0<<" ";
    else g<<d[i]<<" ";
 g<<'\n';
g.close();
}
int main()
{int i,vf,j,dmin;
 initializare();
 for(j=1;j<=n;j++)
  {dmin=inf;
   for(i=1;i<=n;i++)
    if((!m[i])&&(dmin>d[i])&&(d[i]!=inf))
      {dmin=d[i];
       vf=i;
      }
   m[vf]=1;
   for(i=1;i<=n;i++)
    if((!m[i])&&(d[i]>(dmin+c[vf][i])))
      d[i]=dmin+c[vf][i];
  }
 afisare();
return 0;
}