#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 100000000000ll
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct varf {int x, c;};
int n, x0=1;
vector<varf> G[NMAX]; ///liste de adiacenta cu costuri
bool uz[NMAX];
long long int cmin[NMAX];
void citire();
void dijkstra();
void afisare();
class Compar
{
  public:
  bool operator() (int a, int b) ///a si b sunt doua varfuri din graf
  {
    ///min heap
    return cmin[a]>cmin[b];
  }
};
priority_queue<int, vector<int>, Compar> H;

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

void citire()
{int i, j, c, m, k;
 varf aux;
 fin>>n>>m;
 for (k=0; k<m; k++)
     {fin>>i>>j>>c;
      ///in lista de adiacenta a lui i trebuie sa adaug (j,c)
      aux.x=j; aux.c=c;
      G[i].push_back(aux);
     }
  for (i=1; i<=n; i++) cmin[i]=INF;
  cmin[x0]=0;
}
void dijkstra()
{int i, j, vfmin;
 long long int minim;
 H.push(x0);///!!!
while (!H.empty())
     {///calculez vfmin
      vfmin=H.top(); H.pop();
      if (!uz[vfmin])
         {
          uz[vfmin]=1;
          minim=cmin[vfmin];
          if (minim==INF) break;
          ///optimizez eventual costurile minime
          for (j=0; j<G[vfmin].size(); j++)
              if (cmin[G[vfmin][j].x]>minim+G[vfmin][j].c)
                  {cmin[G[vfmin][j].x]=minim+G[vfmin][j].c;
                   H.push(G[vfmin][j].x);///!!!!!
                  }
          }
     }
}
void afisare()
{int i;
 for (i=2; i<=n; i++)
     if (cmin[i]==INF) fout<< 0<<' ';
        else fout <<cmin[i]<<' ';
 fout<<'\n';
}