#include<fstream>
#define INF 32000
using namespace std;
int d[50010],a[250010][4],i,ok,n,m;
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=2;i<=n;i++) d[i]=INF;

    for(i=1;i<=m;i++)
 {
     f>>a[i][1]>>a[i][2]>>a[i][3];
     if(a[i][1]==1) d[a[i][2]]=a[i][3];
 }

 while(!ok)
 {
     ok=1;
     for(i=1;i<=m;i++)
         if(d[a[i][2]]>d[a[i][1]]+a[i][3])
         {
             d[a[i][2]]=d[a[i][1]]+a[i][3];
             ok=0;
         }
  }

for(i=2;i<=n;i++)

 if(d[i]==INF) g<<"0"<<" ";
  else g<<d[i]<<" ";

}