#include <fstream>
#define  INFINIT 1000000000

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,viz[50001],a[1001][1001],m,x,y,d[200000],p,u,coada[1001];
int c[1001][1001],cost,j;
void bell(int nod)
{
  for(int i=1;i<=n;i++)
    d[i]=INFINIT;
    d[nod]=0;
    p=u=1;
    coada[u]=nod;
    while(p<=u)
    {
      j=coada[p];
      p++;
      for(int i=1;i<=n;i++)
        if(c[j][i]!=INFINIT)
        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 l=1;l<=n;l++)
        {
          c[i][l]=INFINIT;
        }
      for(int i=1;i<=m;i++)
        {
          f>>x>>y>>cost;
          c[x][y]=cost;
        }

        bell(1);
        for(int i=2;i<=n;i++)
        g<<d[i]<<" ";

      return 0;
}