#include<fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,poz;
long c[50001];
int sel[50001];
long minim,min2;
int i,j,k,nr;

struct graf
{int nod, cost;
 graf* next;};

graf* b[50001];

void add(int x, int y, int z)
{graf* q = new graf;
 q->cost=z;
 q->nod=y;
 q->next=b[x];
 b[x]=q;
     }

int main()
{f>>n>>m;
int x,y,z;
for(i=1; i<=m; i++)
  {f>>x>>y>>z;
   add(x,y,z);}
c[1]=0;


nr=1;
minim=0;
poz=1;
while(nr)
{

graf* q=b[poz];
while(q)
{ if((c[q->nod]>minim+q->cost && sel[q->nod]==0)||(c[q->nod]==0 && sel[q->nod]==0))
    {c[q->nod]=minim+q->cost;
    nr++;}
  q=q->next;  }
  
minim=10000000;
for(i=1; i<=n; i++)
  if(minim>c[i] && sel[i]==0 && c[i]!=0)
   {poz=i;
    minim=c[i];}
sel[poz]=1;
nr--;
    
}     

minim=10000000;
for(i=2; i<=n; i++)
 g<<c[i]<<" ";

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