#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, gasit;
 long long int minim;
 H.push(x0);///!!!
 for (i=1; i<=n; i++)
     {///calculez vfmin
      gasit=0;////!!!!
      while (!H.empty())
            {vfmin=H.top(); H.pop();
             if (!uz[vfmin]) {gasit=1; break;}
            }
      if (gasit==0) break;
      ///selectez vfmin
      uz[vfmin]=1;
      minim=cmin[vfmin];
      ///optimizez eventual costurile minime
      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';
}