#include <iostream.h>
#include <fstream.h>
#include <values.h>

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct muchie{int sursa, dest; long dist;};
long d[50005];

muchie e[250005];
int n,m;

int main()
{int i,j,x,y;
long c;
fin>>n>>m;

for (i=1;i<=m;i++)
 {fin>>x>>y>>c;
  e[i].sursa=x;
  e[i].dest=y;
  e[i].dist=c;
  if (x==1) d[y]=c;
 }


 for (i=2;i<=n;i++)
  if (d[i]==0)
   d[i]=1005;

c=1;

for (c=1;c==1;)
{c=0;
 for (i=1;i<=m;i++)
  if (d[e[i].dest]>d[e[i].sursa]+e[i].dist)
   {d[e[i].dest]=d[e[i].sursa]+e[i].dist;
    c=1;
   }
}

for (i=2;i<=n;i++)
if (d[i]==1005) fout<<"0 ";
else
fout<<d[i]<<" ";

fout.close();
return 0;
}