#include <fstream>
#include <vector>
#include <set>
#define Nmax 50005
#define INF 1000000005

using namespace std;

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

vector <int> ld[Nmax],lc[Nmax];
int dist[Nmax];
set <pair < int, int> > dij;
set <pair <int, int> > :: iterator w;
int n,m;
int i,c,ii;

int main()
{
  f >> n >> m;
     for (;m;m--)
      {int i,j,c;
          f >> i >> j >> c;
          ld[i].push_back(j);
          lc[i].push_back(c);
      }
    for ( int i = 2 ; i <= n ; i ++ )
     dist[i]=INF;

    dij.insert(make_pair(1,0));

    while(dij.empty()==0)
     {
       i = dij.begin()->first;
       c = dij.begin()->second;
      dij.erase(dij.begin());
      for ( int k = 0 ; k < ld[i].size() ; k ++ )
       {
           ii = ld[i][k];
           if (dist[i]+lc[i][k]<dist[ii])
           {
              w = dij.find(make_pair(ii,dist[ii]));
              if (w != dij.end() )
                dij.erase(w);
              dist[ii]=dist[i]+lc[i][k];
              dij.insert(make_pair(ii,dist[ii]));
           }
       }

     }
    for ( int i = 2 ; i <= n ; i ++ )
      if(dist[i]==INF)
        g << "0 ";
      else
        g << dist[i] << " ";

}