#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;
int d[50001];

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

nod *prim[50001];

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 Citire()
{int i,x,y,cost;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
   {fscanf(f,"%d%d%d",&x,&y,&cost);
    add(prim[x],y,cost);
   }
}

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);
         }
   }
for(i=2;i<=n;i++)
    if(d[i]==inf)
       fprintf(g,"0 ");
    else fprintf(g,"%d ",d[i]);
}

int main()
{
Citire();
Dijkstra();
    return 0;
}