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

vector <pair<int,int> > v[50001];
int n,m,i,y,x,z,vizit[50001],p,u,curent,nr,minim[50001],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));

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