#include<iostream>
#include<fstream>
#include<queue>
 
using namespace std;
 
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

struct Nod
{
    int nod, cost;
    bool operator < (const Nod& e) const
    {
        return cost > e.cost;
    }
};
 
vector <Nod> L[50001]; 
int n,m,cost[50005];
 
priority_queue <Nod> q;
 
void Citire()
{
  int x,y,costt;
  Nod w;
  fin >> n >> m;
  for (int i=1; i<=m; i++)
   {
      fin >> x >> y >> costt;
      w.nod=y;
	  w.cost=costt;     
      L[x].push_back(w);
   }
}
 
void Lee_Bellman_Ford_BFS_Dijkstra()
{
  int i,j,k,costt;
  Nod w,w1;
  w.nod=1;
  w.cost=0;
  q.push(w);
  cost[1]=0;
   
  while (!q.empty())
 {
   w = q.top();
   q.pop();
    
   k = w.nod;
   for (int j=0; j<L[k].size(); j++)
       {
            i = L[k][j].nod; costt = L[k][j].cost;
             
            if (!cost[i] || cost[i] >= cost[k] + costt)
               {
                   cost[i] = cost[k] + costt;
                   w1.nod=i;
                   w1.cost=cost[i];
                   q.push(w1);
               }
       }
 }  
}
 
void Print_that()
{
 for (int i=2; i<=n; i++)
   fout << cost[i] << " ";
 fout << "\n";
}
 
int main ()
{
 Citire();
 Lee_Bellman_Ford_BFS_Dijkstra();
 Print_that();
 fin.close();
 fout.close();
 return 0;
}