#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];

class ComparVf
{public:
 bool operator() (int x, int y)
 {return cmin[x]>cmin[y];}
};

priority_queue <int, vector<int>, ComparVf> 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;
 //initializare
 H.push(p);
 for (i=1; i<=n; i++) cmin[i]=INF;
 cmin[p]=0;
 while (!H.empty())
     {
      vfmin=H.top(); 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
      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; H.push(x);}
          }
     }
}
void afisare()
{int i;
 for (i=2; i<=n; i++)
     if (cmin[i]!=INF) fout<<cmin[i]<<' ';
        else fout<<0<<'\n';
 fout<<'\n';
}