#include <stdio.h>
#include <queue>
#define inf 2000000000
using namespace std;
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

int n,m,d[50005];

struct nod
{int info, cost;
 nod*urm;
};

nod *prim[50005];

class comparvf
{public:
    bool operator()(const int&x, const int&y)
     {return d[x]>d[y];}
};

priority_queue <int, vector <int>, comparvf> H;

void add(nod*&prim, int x, int c)
{nod *p=new nod;
 p->info=x; p->cost=c; p->urm=prim;
 prim=p;
}

void read()
{int i,x,y,cost1;
 fscanf(f,"%d%d",&n,&m);
 for(i=1;i<=m;i++)
    {fscanf(f,"%d%d%d",&x,&y,&cost1);
     add(prim[x],y,cost1);
    }
}

void dijkstra()
{int x, i;
 nod *p;
 for(i=1;i<=n;i++) d[i]=inf;
 d[1]=0;
 H.push(1);
 while(!H.empty())
  { x=H.top(); H.pop();
 for(p=prim[x];p!=NULL;p=p->urm)
    if(d[x]+p->cost<d[p->info])
     { d[p->info]=d[x]+p->cost;
       H.push(p->info);
     }
  }
}

void print()
{int i;
 for(i=2;i<=n;i++)
    if(d[i]==inf)
      fprintf(g,"0 ");
    else
      fprintf(g,"%d ",d[i]);
}

int main()
{ read();
  dijkstra();
  print();
  return 0;
}