#include <vector>
#include <unordered_map>
#include <cassert>
#include <iostream>

using namespace std;

int N, M;
int S, D;
vector<pair<int, int>> *g;
int *d, *p;
int *h, *hpos, hsize = 0;
bool *in_heap;

void heap_swap(int i1, int i2) {
  std::swap(h[i1], h[i2]);
  hpos[h[i1]] = i1;
  hpos[h[i2]] = i2;
}

void heap_up(int index) {
  while(index > 1) {
    int p_index = index / 2;
    if(d[h[index]] >= d[h[p_index]])
      break;
    heap_swap(index, p_index);
    index = p_index;
  }
}

void heap_down(int index) {
  while(1) {
    int idx_min = index;
    int left_index = 2 * index;
    int right_index = 2 * index + 1;
    if(left_index <= hsize && d[h[left_index]] < d[h[idx_min]]) idx_min = left_index;
    if(right_index <= hsize && d[h[right_index]] < d[h[idx_min]]) idx_min = right_index;
    if(index == idx_min)
      break;
    heap_swap(index, idx_min);
    index = idx_min;
  }
}

int heap_front() {
  return h[1];
}

void heap_pop() {
  in_heap[h[1]] = false;
  heap_swap(1, hsize);
  --hsize;
  heap_down(1);
}

void heap_push(int node) {
  ++hsize;
  h[hsize] = node;
  hpos[node] = hsize;
  in_heap[node] = true;
  heap_up(hsize);
}

void alloc_resources() {
  g = new vector<pair<int, int>>[N];
  d = new int[N];
  p = new int[N];
  h = new int[N + 1];
  in_heap = new bool[N];
  hpos = new int[N];
}

void free_resources() {
  delete[] g;
  delete[] d;
  delete[] p;
  delete[] h;
  delete[] hpos;
  delete[] in_heap;
}

void read_graph() {
  scanf("%d%d", &N, &M);
  alloc_resources();
  for(int i = 0; i < M; ++i) {
    int x, y, c;
    scanf("%d%d%d", &x, &y, &c);
    x--, y--;
    g[x].push_back(make_pair(y, c));
//    g[y].push_back(make_pair(x, c));
  }
  // scanf("%d%d", &S, &D);
  S = 0;
  D = N - 1;
}

bool on_min_path(int x, int y) {
  // TODO check whether edge (x, y) is on the shortest path from S to D.
  return false;
}

void solve_query(int x, int y) {
  if(on_min_path(x, y)) {
    // TODO removing an edge on the min path.
  } else {
    printf("%d\n", d[D]);
  }
}

void solve_queries() {
  int Q;
  scanf("%d", &Q);
  while(Q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    solve_query(x, y);
  }
}

const int INFINITY = 1 << 29;

void dijkstra() {
  for(int i = 0; i < N; i++) {
    d[i] = INFINITY;
    p[i] = -1;
  }

  d[S] = 0;
  for(int i = 0; i < N; i++) heap_push(i);

  while(hsize > 0) {
    int node = heap_front();
    heap_pop();
    for(pair<int, int> node_info : g[node]) {
      int vecin = node_info.first;
      int cost = node_info.second;
      if(d[vecin] > d[node] + cost) {
        d[vecin] = d[node] + cost;
        p[vecin] = d[node];
        assert(in_heap[vecin]);
        heap_up(hpos[vecin]);
      }
    }
  }

  for(int i = 1; i < N; i++) {
    printf("%d ", d[i] == INFINITY ? 0 : d[i]);
  }
  printf("\n");
}

void prepare_answers() {
  dijkstra();
  // TODO
}

int main() {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  read_graph();
  prepare_answers();
  // solve_queries();
  free_resources();
  return 0;
}