#include <fstream>
#define inf 100000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[1000000],x,y,z,m,cost,c[1000][1000],n,p,u,coada[100000],j,i,s;
void bellmanford(int nod)
{
  for(i=1;i<=n;i++)
    d[i]=inf;
  d[nod]=0;
  p=u=1;
  coada[u]=nod;
  while(p<=u)
  {
    j=coada[p];
    p++;
    for(i=1;i<=n;i++)
      if(c[j][i]!=inf)
      if(d[i]>d[j]+c[j][i])
    {
      d[i]=d[j]+c[j][i];
      coada[++u]=i;
    }
  }

}
int main()
{
   f>>n>>m;
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        c[i][j]=inf;
   for(int i=1;i<=m;i++)
   {
       f>>x>>y>>z;
       c[x][y]=z;
   }
   bellmanford(1);
   for(int i=2;i<=n;i++)
   if(d[i]==inf)
    g<<0<<" ";
    else
    g<<d[i]<<" ";
   f.close();
   g.close();
    return 0;
}