#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 1000000000
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];
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, minim, vfmin,gasit=0;
 H.push(x0);
 for (i=1; i<=n; i++)
     {
      vfmin=-1;////!!!!
      while (!H.empty())
            {vfmin=H.top(); H.pop();
             if (!uz[vfmin])
             {
                 gasit=1;
                 break;
             }
            }
      if (gasit==0) break;

      uz[vfmin]=1;
      minim=cmin[vfmin];

      for (j=0; j<G[vfmin].size(); j++)
            if (!uz[G[vfmin][j].x] &&
                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';
}