#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define inf 0x3f3f3f
#define nod first
#define cost second
using namespace std;

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

int n, m;
vector<int> d(nmax, inf);
vector<bool> viz(nmax, false);
vector< pair<int,int> > v[nmax];
queue<int> q;

void citeste()
{ int x, y, c;

    in>>n>>m;
     for (int i=1; i<=m; ++i)
      {
          in>>x>>y>>c;
          v[x].push_back(make_pair(y,c));
      }
}

void dijkstra()
{ int k;

    q.push(1);
    d[1] = 0;
    viz[1] = true;

    while ( !q.empty() )
     {
        k = q.front();
        q.pop();
        viz[k] = false;
         for (unsigned int i = 0; i < v[ k ].size(); ++i)
          {
              d[ v[ k ][i].nod ] = min( d[ v[k][i].nod ], d[ k ] + v[ k ][i].cost );

              if ( !viz[ v[ k ][i].nod ] )
               {
                   viz[ v[ k ][i].nod ] = true;
                   q.push( v[ k ][i].nod );
               }
          }

     }


}
int main()
{

    citeste();

    dijkstra();

    for (int i=2; i<=n; ++i)
     if ( d[i] == inf ) out<<"0 ";
      else out<<d[i]<<" ";

return 0;
}