#include<fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,poz;
int a[250001][3];
int c[50001],sel[50001],minim;
int i,j,k,nr;

int main()
{f>>n>>m;
for(i=1; i<=m; i++)
  f>>a[i][0]>>a[i][1]>>a[i][2];
c[1]=0;
for(i=2; i<=n; i++)
  c[i]=1001;

nr=n;
while(nr)
{minim=1001;
for(i=1; i<=n; i++)
  if(minim>c[i] && sel[i]==0)
   {poz=i;
    minim=c[i];}
sel[poz]=1;
nr--;
for(i=1; i<=m; i++)
  if(a[i][0]==poz && sel[a[i][1]]==0 && c[a[i][1]]>minim+a[i][2])
     c[a[i][1]]=minim+a[i][2];
    
}     

for(i=2; i<=n; i++)
 g<<c[i]<<" ";

f.close();
g.close();
return 0;}