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

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define infinity 100000
#define Nmax 50001
class compare{
public:
  bool operator()( pair<int,int> a , pair<int,int> b)
  {
    return a.second > b.second;
  }
};

vector<pair<int,int> > vec[Nmax];
vector<pair<int,int> >::iterator it;
priority_queue<pair<int,int> ,vector<pair<int,int> >,compare> coada;

void dij(int plecare,int dim)
{
  int dist[dim+1];
  bool vazut[dim+1];
  for(int i = 1; i <= dim; i++)
  {
    vazut[i] = false;
    dist[i] = infinity;
  }
  dist[plecare] = 0;
  coada.push(make_pair(plecare,dist[plecare]));
  int min;
  while(!coada.empty())
  {
    min = coada.top().first;
    coada.pop();
    if(!vazut[min])
    {
      vazut[min] = true;
      for(it = vec[min].begin();it != vec[min].end();it++)
      {
        if(dist[it->first] > dist[min] + it->second)
        {
          dist[it->first] = dist[min] + it->second;
          if(vazut[it->first] == false)
            coada.push(make_pair(it->first,dist[it->first]));
        }
      }
    }
  }
  for(int i =2;i <= dim;i++)
  {
    if(dist[i] == infinity)
      out<<'0'<<' ';
    else
      out<<dist[i]<<' ';
  }
}
int main()
{
  int dim,muchii,x,y,val;
  in >> dim >> muchii;
  for(int i = 1 ; i <= muchii;i++)
  {
    in >> x >> y >> val;
    vec[x].push_back(make_pair(y,val));
  }
  dij(1,dim);
  return 0;
}