#include <fstream>
#include <vector>
#include <queue>

#define lmax 50005

using namespace std;

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

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

priority_queue <int> q;

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

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.push(1);

    while (q.size())
      {
          nodcurent=q.top();
          q.pop();

          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.push(v[nodcurent][i].first);
              }
      }

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

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

     else

      g<<0<<" ";


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