#include<iostream.h>
#include<fstream.h>
struct nod {
           int x,c;
           nod *next;
           }*a[50001],*p;

int v[50001],s[50001],i,j,n,m,inf=1<<30,min,poz;
int main()
{
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
fin>>n>>m;
for(i=1;i<=n;i++)v[i]=inf;
for(i=1;i<=m;i++){
                 p=new nod; 
                 fin>>j>>p->x>>p->c;
                 p->next=a[j];
                 a[j]=p;
                 }
s[1]=1;
p=a[1];
while(p){
        v[p->x]=p->c;
        p=p->next;
        }
for(i=2;i<=n;i++)
   {
   poz=0;
   min=inf;
   for(j=2;j<=n;j++)if(!s[j] && v[j]<min){
                                         min=v[j];
                                         poz=j;
                                         }
   s[poz]=1;
   if(poz){
          p=a[poz];
          while(p){
                  if(!s[p->x])
                    if(v[p->x]>v[poz]+p->c)v[p->x]=v[poz]+p->c;
                  p=p->next;
                  }  
          } 
   }
for(i=2;i<=n;i++)if(v[i]!=inf)fout<<v[i]<<' ';
                 else fout<<"0 ";
return 0;
}