#include<fstream>
#define INF 1<<30
using namespace std;
int d[50010],a[50010],b[50010],c[50010],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]>>b[i]>>c[i];

   if(a[i]==1) d[b[i]]=c[i];
 }

while(!ok)

 { ok=1;

    for(i=1;i<=m;i++)

     if( d[b[i]] > d[a[i]]+c[i] )

       d[b[i]]=d[a[i]]+c[i], ok=0;
  }
for(i=2;i<=n;i++)

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

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