#include <bits/stdc++.h>
#define NMAX 50005
#define INF 2e9
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m;
int path[NMAX];
vector< pair < int, int > > nodes[NMAX];
priority_queue < pair < int, int > > pq;

void read(){
  int x, y, cost;
  f>>n>>m;
  while(m--){
    f>>x>>y>>cost;
    nodes[x].push_back({y, cost});
  }
  for(int i = 2; i <= n; ++i)
    path[i] = INF;
  f.close();
}

void dijkstra(int node){
  int cost, next_node;
  path[node] = 0;
  pq.push({0, node});
  while(!pq.empty()){
    next_node = pq.top().second;
    cost = -pq.top().first;
    pq.pop();
    if(path[next_node] != INF && path[next_node] != 0)
      continue;
    path[next_node] = cost;
    for(auto it:nodes[next_node])
      if(path[it.first] > cost + it.second)
        pq.push({-(cost+it.second), it.first});
  }
}

int main(){
  read();
  dijkstra(1);
  for(int i = 2; i <= n; ++i)
    if(path[i] == INF)
      g << 0 << ' ';
    else
      g << path[i] << ' ';
  g.close();
}