#include<fstream.h>
#define max 200000000
 ifstream f("dijkstra.in");
 ofstream g("dijkstra.out");
    int n,m;

struct nod
{
 int a,b,dist;
 nod *urm;
} *pr;

long d[50010];

void add(int x,int y,int z)
{
 nod *q=new nod;
 q->a=x;
 q->b=y;
 q->dist=z;
 q->urm=pr;
 pr=q;
}

void ford()
{
 int i,ok;
 for(i=2;i<=n;i++)
  if(d[i]==0)
    d[i]=max;
 ok=1;
 while(ok==1)
 {
  ok=0;
  nod *q;
  for(q=pr;q;q=q->urm)
  {
   if(d[q->b]>d[q->a]+q->dist)
    d[q->b]=d[q->a]+q->dist,ok=1;
  }

 }


}
int main()
{  int i,x,y,z;
 f>>n>>m;
 for(i=1;i<=n;i++)
 {
  f>>x>>y>>z;
  add(x,y,z);
  if(x==1) d[y]=z;
 }
 ford();
 for(i=2;i<=n;i++)
   g<<d[i]<<" ";

 return 0;
}