#include <fstream>
#include <vector>

#define lmax 50005

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <pair <int,int> >v[lmax];

int q[5*lmax];

int n,m,x,y,z,nodcurent,p,u;

int dist[lmax];

int main()
{
    f>>n>>m;

    for (int i=1;i<=m;i++)
     {
         f>>x>>y>>z;

         v[x].push_back(make_pair(y,z));
     }

    for (int i=1;i<=n;i++)
     dist[i]=1005*lmax;

    dist[1]=0;

    q[1]=1;
    p=u=1;

    while (p<=u)
      {
          nodcurent=q[p++];

          for (int i=0;i<v[nodcurent].size();i++)
            if (dist[v[nodcurent][i].first]>dist[nodcurent]+v[nodcurent][i].second)
              {
                  dist[v[nodcurent][i].first]=dist[nodcurent]+v[nodcurent][i].second;

                  q[++u]=v[nodcurent][i].first;
              }
      }

    for (int i=2;i<=n;i++)
     if (dist[i]!=1005*lmax)

      g<<dist[i]<<" ";

     else

      g<<0<<" ";


   f.close();
   g.close();
}