#include<fstream>
using namespace std;
struct nod{int info,dist; nod*adr;} *v[50001],*p;
int n,m,i,j,x,y,c,d[50001],drum[50001],inf=32767,minn,poz;
int bellman_ford(int nod) 
{
   int ok, i, j, k;
   for (i=1;i<=n;i++) d[i] = inf;
    d[nod]=0;

      for (j=1;j<=n;j++)
	  {
		p=v[j];
         while(p)
		 {
            if (d[j]!=inf && p->dist!=inf)
               if (d[p->info] > d[j] + p->dist)
               {
                   d[p->info] = d[j] + p->dist;
                  //drum[p->info] = j;
               }
			p=p->adr;
		 }
	  
   } 
}
int main()
{
	ifstream f("dijkstra.in");ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		p=new nod; p->info=y; p->dist=c; p->adr=v[x]; v[x]=p;
	}
	bellman_ford(1);
	for(i=2;i<=n;i++) d[i]==inf?g<<"0 ":g<<d[i]<<" ";
	f.close();g.close();
return 0;}