#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50002
#define INF 1000000002

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, p=1;

vector < pair<int, int> > G[NMAX];
int cmin[NMAX];
bool uz[NMAX];
/*class ComparVf
{public:
 bool operator() (int x, int y)
 {return cmin[x]>=cmin[y];}
};
*/
priority_queue <pair<int,int>, vector<pair<int,int>>, greater< pair<int,int> > > H;

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

void citire()
{int i, j, c, m, k;
 pair<int, int> vf;
 fin>>n>>m;
 for (k=0; k<m; k++)
      {fin>>i>>j>>c;
       //am arc de la i la j de cost c
       //in lista de adiacenta a lui i trebuie sa punem vf j si costul c
       vf.first=j; vf.second=c;
       G[i].push_back(vf);
      }
}

void dijkstra()
{int i, x, vfmin, c;
pair <int, int> pp;
 //initializare
 pp.first=0; pp.second=p;
 H.push(pp);
 for (i=1; i<=n; i++) cmin[i]=INF;
 cmin[p]=0;
 while (!H.empty())
     {
      vfmin=H.top().second; H.pop();
      if (cmin[vfmin]==INF) break;
      //vfmin este selectat
      //optimizez eventual costurile catre celelalte varfuri, trecand prin vfmin
      //parcurg lista de adiacenta a lui vfmin
      if (!uz[vfmin])
          for (i=0; i<G[vfmin].size(); i++)
              {x=G[vfmin][i].first; c=G[vfmin][i].second;
                 if (cmin[x]>cmin[vfmin]+c)
                      {cmin[x]=cmin[vfmin]+c;
                       pp.first=cmin[x]; pp.second=x;
                       H.push(pp);}
              }
      uz[vfmin]=1;
     }
}
void afisare()
{int i;
 for (i=2; i<=n; i++)
     if (cmin[i]!=INF) fout<<cmin[i]<<' ';
        else fout<<0<<' ';
 fout<<'\n';
}