#include <fstream>

#include <queue>
#define NMAX 50000
#define INF (1<<30)
using namespace std;

int sol[NMAX + 1];

struct nod{

  int node, cost;
  bool operator < (const nod &other) const{
      return cost > other.cost;
  }
};
priority_queue <nod> q;
vector <nod> v[NMAX + 1];
void dijkstra (){
    int current_node;
    int current_dist;
    while (!q.empty()){
      current_node = q.top().node;
      current_dist = q.top().cost;
      q.pop();
      if (sol[current_node] == INF){
        sol[current_node] = current_dist;

        for (int i = 0; i < v[current_node].size(); i++){
          if (sol[v[current_node][i].node] == INF)
            q.push({v[current_node][i].node, current_dist + v[current_node][i].cost});
        }
      }
    }
}
int main(){

  ifstream fin ("dijkstra.in");
  ofstream fout ("dijkstra.out");
  int n, m;
  fin >> n >> m;

  int a, b, c;
  for (int i = 0; i < m; i++){
   fin >> a >> b >> c;
   v[a].push_back({b,c});
  }
  for (int i = 1; i <= n; i++)
    sol[i] = INF;
  q.push({1, 0});
  dijkstra();
  for (int i = 2; i <= n; i++){
    if (sol[i] == INF)
      sol[i] = 0;
    fout << sol[i] << " ";
  }

  return 0;
}