#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
class heap
{
 public :
  int nod;
  int price;
 bool operator < (const heap & other_node ) const
 {
  return this->price > other_node.price;
 }
};
struct edge
{
 int node , cost;
};
vector < edge > v[50005];
priority_queue < heap > pq ;
int dist[50005];
bool was[50005];
const int oo = 0x7fffffff;
int main()
{ int Nrnodes , Nredges ;
  fin >> Nrnodes >> Nredges;
  for(int i = 2 ; i <= Nrnodes ; i++)
    dist[i] = oo ;
  int edge1 , edge2 , cost;
  for(int i = 1 ; i <= Nredges ; i ++)
  {
    fin >> edge1 >> edge2 >> cost ;
    v[edge1].push_back(edge{edge2,cost});
  }
  pq.push(heap{1,0});
  while(pq.empty()==0)
  {
   int costmin = pq.top().price;
   int nodul = pq.top().nod;
   pq.pop();
   if(costmin == dist[nodul])
   {

   for(int i = 0 ; i < (int)v[nodul].size() ; i++)
     if(costmin + v[nodul][i].cost < dist[v[nodul][i].node])
     {
      dist[v[nodul][i].node] = costmin + v[nodul][i].cost ;
      pq.push(heap{v[nodul][i].node,dist[v[nodul][i].node]});
     }
  }
  }
  for(int i = 2 ; i <= Nrnodes ; i++)
    if(dist[i] == oo)
     fout << 0 << " ";
    else
     fout << dist[i] << " " ;
    return 0;
}