#include <stdio.h>
#include <iostream>
#define inf 2000000000
#include <queue>
using namespace std;

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

struct nod {int info,cost; nod *urm;};
nod *prim[50001];
int n,m;
int d[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 y)
{  nod *p=new nod;
   p->info=x; p->cost=y; 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 Dijskstra()
{   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;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();
    Dijskstra();
    return 0;
}