#include<iostream.h>
#include<fstream.h>
long i,j,k,n,m,a[250010][3],c[50010],ok;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{f>>n>>m;
for(i=2;i<=n;i++)
        c[i]=50000001;
for(i=1;i<=m;i++)
        {f>>a[i][0]>>a[i][1]>>a[i][2];
          if(a[i][0]==1) c[a[i][1]]=a[i][2];}
while(!ok)
{ok=1;
for(j=1;j<=m;j++)
         if(c[a[j][2]] > c[a[j][1]] + a[j][3])
                                 {c[a[j][1]]=c[a[j][0]]+a[j][2];
                                  ok=0;}
}
for(i=2;i<=n;i++)
     if(c[i]<50000001)  g<<c[i]<<" ";
                else  g<<"0 ";
return 0;
}