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

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

const long inf=MAXLONG-1000;

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

muchie e[250005];
long n,m;

int main()
{long 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]=inf;


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]==inf) fout<<"0 ";
else
fout<<d[i]<<" ";

fout.close();
return 0;
}