#include <vector>
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <pair<int,int> > v[1000];
int n,m,i,y,x,z,vizit[50001],p,u,curent,nr,minim[1000],vizitat[50001];
int main()
{
     f>>n>>m;
     for (i=1;i<=m;i++)
      {
          f>>y>>x>>z;
          v[y].push_back(make_pair(x,z));

      }
      vizit[1]=1;
      vizitat[1]=1;
      for (i=2;i<=n;i++)
       minim[i]=100000l;
      p=0;
      u=1;
      nr=1;
      while (nr<n)
       {
           p++;
           curent=vizit[p];
           for (i=0;i<=v[vizit[p]].size()-1;i++)
           {
               if (vizitat[v[curent][i].first]==0)
               {if (minim[curent]+v[curent][i].second<minim[v[curent][i].first])
               minim[v[curent][i].first]=minim[curent]+v[curent][i].second;
               nr++;
               vizitat[v[curent][i].first]=1;
               u++;
               vizit[u]=v[curent][i].first;}
           }
       }
       for (i=2;i<=n;i++)
        g<<minim[i]<<" ";
    f.close();
    g.close();
}