#include <cstdio>
#include <set>
#include <vector>
#define DMAX 50005
#define INF 2000000000

using namespace std;

struct muchie
{
int vf,cost;
};

vector <muchie> G[DMAX];
set <pair<int,int> > Q;

FILE*fin=fopen("dijkstra.in","r");
FILE*fout=fopen("dijkstra.out","w");

int n,m,vfs;
int CF[DMAX];

void citire();
void init();
void dijkstra();
void afisare();

int main()
{
int i;
citire();
init();
dijkstra();
afisare();
    return 0;
}

void citire()
{
int i,x,y,cost;
muchie aux;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
    {
     fscanf(fin,"%d %d %d",&x,&y,&cost);
     aux.vf=y; aux.cost=cost;
     G[x].push_back(aux);
    }
}

void init()
{
int i;
vfs=1;
for (i=1;i<=n;i++) CF[i]=INF;
CF[vfs]=0;
Q.insert( make_pair(0,vfs) );
}

void dijkstra()
{
int vf,minim;
int i;
while(Q.size()>0)
     {
      minim=(*Q.begin()).first;
      vf=(*Q.begin()).second;
      Q.erase(*Q.begin());
      for (i=0;i<G[vf].size();i++)
           if (CF[ G[vf][i].vf ]>G[vf][i].cost+minim)
              {
               CF[ G[vf][i].vf ]=G[vf][i].cost+minim;
               Q.insert( make_pair(CF[ G[vf][i].vf ],G[vf][i].vf) );
              }
     }
}

void afisare()
{
int i;
for (i=2;i<=n;i++)
     if (CF[i]!=INF)
         fprintf(fout,"%d ",CF[i]);
         else
         fprintf(fout,"0 ");
fprintf(fout,"\n");
}