#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

const int nmax = 5e4;
const int INF = 1e6;

struct dijkstra {
  int node, cost;
  bool operator<(const dijkstra &other)const{
    return other.cost < cost;
  }
};

vector <dijkstra> graf[nmax + 1];

priority_queue <dijkstra> pq;

int dist[nmax + 1];

void drumin (){

  memset (dist, INF, sizeof(dist));

  pq.push({1, 0});
  dist[1] = 0;

  while (!pq.empty()){
    int curnode = pq.top().node;
    int curdist = pq.top().cost;
    pq.pop();

    for (auto neighbour: graf[curnode]){
      if (dist[neighbour.node] > curdist + neighbour.cost){
        dist[neighbour.node] = curdist + neighbour.cost;
        pq.push({neighbour.node, curdist + neighbour.cost});
      }
    }
  }
}

int main(){

  ifstream fin ("dijkstra.in");
  ofstream fout ("dijkstra.out");

  int n, m;
  fin >> n >> m;

  for (int i = 0; i < m; i++){
    int a, b, c;
    fin >> a >> b >> c;

    graf[a].push_back({b, c});
  }

  drumin();
  for (int i = 2; i <= n; i++){
    fout << dist[i] << " ";
  }
  return 0;
}