#include <memory>
#include <forward_list>
#include <cstdlib>
#include <fstream>
#include <utility>
#include <limits>
#include <iostream>

class Graph {
public:
   using VType = uint16_t;
   using DistanceT = uint16_t;
   using Vecinity = std::pair<VType, DistanceT>;
   using VList = std::forward_list<Vecinity>;
   const size_t vCount;

   explicit Graph(size_t count):
       vCount(count),
       m_adj(std::make_unique<VList[]>(count))
    {}

   const VList& getAdj(VType v) const {
     return m_adj[v];
   }

   void insertAdj(VType v, VType u, DistanceT d) {
      m_adj[v].push_front(std::make_pair(u, d));
   }

private:
   std::unique_ptr<VList[]> m_adj;
};

Graph read(const char* path)
{
  size_t n, m;
  std::ifstream fin(path);
  fin >> n >> m;
  Graph g(n);
  for (size_t i = 0; i < m; ++i) {
    Graph::VType u,v;
    Graph::DistanceT d;
    fin >> u >> v >> d;
    g.insertAdj(u - 1, v - 1, d);
  }
  return g;
}

template <typename CmpT, typename ElementT>
class Heap {
public:
  Heap(size_t n, CmpT&& cmp):
     m_n(n),
     m_cmp(std::move(cmp)),
     m_heap(std::make_unique<ElementT[]>(n)),
     m_rheap(std::make_unique<size_t[]>(n))
  {
     for (size_t i = 0; i < n; ++i) {
       m_heap[i] = i;
       m_rheap[i] = i;
     }
  }

 void heapUp(ElementT el) {
    doHeapUp(m_rheap[el]);
 }

ElementT pop() {
    // assert(m_n);
    ElementT result = m_heap[0];
    swap(0, m_n - 1);
    --m_n;
    doHeapDw(0);
    return result;
}

size_t length() { return m_n; }

private:

  void doHeapUp(size_t index)
  {
     while(index) {
        size_t pIndex = (index - 1) / 2;
        auto cmp = m_cmp(m_heap[pIndex], m_heap[index]);
        if (cmp <= 0) break;
        swap(pIndex, index);
        index = pIndex;
     }
  }

void doHeapDw(size_t index)
{
  while (index < m_n) {
    size_t toSwap = index;
    size_t left = index * 2 + 1;

    if (left >= m_n) break;
    if (m_cmp(m_heap[index], m_heap[left]) > 0) toSwap = left;

    size_t right = left + 1;
    if (right < m_n && m_cmp(m_heap[toSwap], m_heap[right]) > 0) toSwap = right;
    if (toSwap == index) break;
    swap(index, toSwap);
    index = toSwap;
  }
}

void swap(size_t i, size_t j) {
  ElementT aux = m_heap[i];
  m_heap[i] = m_heap[j];
  m_heap[j] = aux;
  m_rheap[m_heap[i]] = i;
  m_rheap[m_heap[j]] = j;
}


  size_t m_n;
  CmpT m_cmp;
  std::unique_ptr<ElementT[]> m_heap;
  std::unique_ptr<size_t[]> m_rheap;
};

template <typename ElementT, typename CmpT>
Heap<CmpT, ElementT> makeHeap(size_t n, CmpT&& cmp) {
    return Heap<CmpT, ElementT>(n, std::move(cmp));
}

std::unique_ptr<uint32_t[]> dijkstra(const Graph& g,  const Graph::VType src)
{
  std::unique_ptr<uint32_t[]> result = std::make_unique<uint32_t[]>(g.vCount);
  auto h = makeHeap<Graph::VType>(g.vCount, [&result](Graph::VType e1, Graph::VType e2) {
    return int64_t(result[e1]) - int64_t(result[e2]);
});
  for (size_t i = 0; i < g.vCount; ++i) {
    result[i] = std::numeric_limits<uint32_t>::max();
  }
result[src] = 0;
h.heapUp(src);
while (h.length()) {
   auto el = h.pop();
   if (result[el] == std::numeric_limits<uint32_t>::max()) {
       break;
   }
   for (const auto& adj : g.getAdj(el)) {
     if (result[adj.first] > (result[el] + uint32_t(adj.second))) {
        result[adj.first] = result[el] + uint32_t(adj.second);
        h.heapUp(adj.first);
     }
   }
 }
 return result;
}

int main() {
   auto g = read("dijkstra.in");
   auto d = dijkstra(g, 0);

   std::ofstream fout("dijkstra.out");
   for (size_t i = 1; i < g.vCount; ++i) {
     fout << (d[i] < std::numeric_limits<uint32_t>::max() ? d[i] : 0) << " ";
   }
   fout << std::endl;
   return 0;
}