#include<fstream.h>
#define max 50000
#define maxm 250000

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,m,d[max];
struct nod{int x,y,c;
	  } a[maxm];

void citire()
{int i;
 fin>>n>>m;
 for(i=1;i<=m;i++)
 {fin>>a[i].x>>a[i].y>>a[i].c;
  if(a[i].x==1) d[a[i].y]=a[i].c;
  }

 for(i=1;i<=n;i++)
 if(d[i]==0) d[i]=max;
 }

int main()
{int i,cc,x,y;
 citire();

 for(cc=1;cc==1;)
 {cc=0;
  for(i=2;i<=m;i++)
  {x=a[i].x;
   y=a[i].y;
   if(d[y]>d[x]+a[i].c)
   {d[y]=d[x]+a[i].c;
    cc=1;
    }
   }
  }

 for(i=2;i<=n;i++)
 fout<<d[i]<<" ";

 fin.close();
 fout.close();
 return 0;
 }