#include <fstream>
#include <queue>
#define inf 1000009;
using namespace std;
ifstream d("dijkstra.in");
ofstream o("dijkstra.out");
int n,m,a,b,c,i,j,t,ad[5000][5000],e[50009],n1,n2,vec,ht,hb,k;
struct vf{int no,apr;};
vf hp[50009];
bool vr[50009];
inline bool cmp(vf x, vf y) {return x.apr>y.apr;};
int main()
  {
    d>>n>>m;
    for (i=1;i<=n;i++) for (j=1;j<=n;j++) ad[i][j]=-1;
    ht=2;hb=n;
    for (i=1;i<=n;i++) {hp[i].no=i; hp[i].apr=inf; e[i]=inf;}
    hp[1].apr=0; e[1]=0;
    for (i=1;i<=m;i++) {d>>a>>b>>c; ad[a][b]=c;};

    n1=1; vr[1]=1;
        for (i=1;i<=n;i++)
          if ((ad[n1][i]>=0)&(!vr[i]))
            if (hp[i].apr>hp[n1].apr+ad[n1][i])
              {e[i]=hp[i].apr=hp[n1].apr+ad[n1][i];};
        vr[n1]=1;
    make_heap(hp+ht,hp+hb,cmp);
    while (ht!=hb)
      {
        n1=hp[ht].no;
        for (i=1;i<=n;i++)
          if ((ad[n1][i]>=0)&(!vr[i]))
            if (e[i]>e[n1]+ad[n1][i])
              {e[i]=e[n1]+ad[n1][i]; for (k=ht;k<=n;k++) hp[k].apr=e[hp[k].no];};
        vr[n1]=1;
        ht++;make_heap(hp+ht,hp+hb,cmp);
      };
    for (i=2;i<=n;i++)
      if (e[i]==1000009) o<<0<<' ';
        else o<<e[i]<<' ';
  };