#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define Nmax 50005
using namespace std;
ifstream scan("dijkstra.in");
ofstream print("dijkstra.out");
vector < pair < int , int > > v[Nmax];
const int infinit = 1000000000;
struct nod {
int a , b , cost ;
}node;
int costmin[Nmax];
int main()
{ int Nrnodes , Nredges , i;
  scan >> Nrnodes >> Nredges;
  for(i = 0 ; i < Nredges ; i++)
   {
    scan >> node.a >> node.b >> node.cost;
    v[node.a].push_back(make_pair(node.b,node.cost));
   }
  for(int i = 2 ; i <= Nrnodes ; i ++ )
    costmin[i] = infinit;
  queue <int> q;
  q.push(1);
  costmin[1] = 0;
  while(q.empty() == 0)
  {
    int x = q.front();
    for(vector <pair<int,int> >::iterator it=v[x].begin();it!=v[x].end();it++)
     if(costmin[x] + it->second  < costmin[it->first])
     {
      costmin[it->first] = costmin[x] + it->second;
      q.push(it->first);
      cout << it->first << " ";
     }
    q.pop();
  }
  for(i = 2 ; i <= Nrnodes ; i ++)
    print << costmin[i] << " ";
    return 0;
}