#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;
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;
for(i=2; i<=n; i++)
  c[i]=10000000;

nr=n;
while(nr)
{minim=10000000;
for(i=1; i<=n; i++)
  if(minim>c[i] && sel[i]==0)
   {poz=i;
    minim=c[i];}
sel[poz]=1;
nr--;

graf* q=b[poz];
while(q)
{ if(c[q->nod]>minim+q->cost)
    c[q->nod]=minim+q->cost;
  q=q->next;  }

    
}     

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

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