#pragma GCC optimize("O3")
#define NDEBUG
#include <vector>
#include <cstdint>
#include <cassert>
#include <string>
#include <algorithm>
namespace ja::AdvancedDataStructures::FibonacciHeap {
#ifndef jassert
#define jassert(expr, msg, ...) assert(expr && msg)
#endif // jassert
#ifndef jlog
#define jlog(...) ((void)0)
#endif // jlog
template < typename DATA, typename OPS >
class FibonacciHeap {
public:
struct Node { // This has to be public, since it's also the index for decrease_key()
DATA key; int32_t degree; bool mark;
Node *left, *right, *parent, *child;
Node(const DATA& _value) {
key = _value; degree = 0; mark = false;
left = right = this;
parent = child = nullptr;
}
};
private:
Node *heap_min;
size_t node_count;
OPS op{};
void _erase(Node *a) {
if(a == nullptr) return;
for(Node *b = a->right; b != a;) {
_erase(b->child);
Node *next_b = b->right;
delete b;
b = next_b;
}
_erase(a->child); delete a;
}
Node* _merge(Node *a, Node *b) {
if(a == nullptr || b == nullptr) return (a ? a : b);
if( op.less(b->key, a->key) ) std::swap(a, b); // Make sure you have to merge b into a (a remains heap_min)
// Connect the two circular lists
Node *a_right = a->right, *b_left = b->left;
a->right = b; b->left = a;
a_right->left = b_left; b_left->right = a_right;
return a;
}
void _extract_from_circular_list(Node *node) {
if(node->right == node) return;
Node *l = node->left, *r = node->right;
l->right = r; r->left = l;
node->left = node->right = node;
}
void _insert_node(Node *new_node) {
heap_min = _merge(heap_min, new_node);
}
void _remove_parents_from_circular_list(Node *node) {
if(node == nullptr) return; // there is no element in the circular list
Node *oth = node;
do { oth->parent = nullptr; oth = oth->right; } while(oth != node);
}
Node* _add_child(Node *parent, Node *child) {
if( op.less(child->key, parent->key) ) std::swap(parent, child);
parent->degree += 1;
parent->child = _merge(parent->child, child);
child->parent = parent;
return parent;
}
DATA _get_min() {
return heap_min->key;
}
void _consolidate() {
const int MAX_DEGREE = 24; int max_degree = 0;
static Node* root_by_degree[MAX_DEGREE] = {nullptr,};
if(heap_min == nullptr) return; // nothing to consolidate
Node *to_consolidate;
do {
to_consolidate = heap_min->right;
_extract_from_circular_list(to_consolidate);
for(int deg = to_consolidate->degree; deg < MAX_DEGREE; deg += 1) {
if(root_by_degree[deg] == nullptr) {
if(deg > max_degree) max_degree = deg;
root_by_degree[deg] = to_consolidate;
break;
}
else {
to_consolidate = _add_child(to_consolidate, root_by_degree[deg]);
root_by_degree[deg] = nullptr;
}
}
} while(to_consolidate != heap_min);
heap_min = nullptr;
for(int deg = max_degree; deg >= 0; deg -= 1) {
heap_min = _merge(heap_min, root_by_degree[deg]);
root_by_degree[deg] = nullptr;
}
}
void _pop_min() {
if(heap_min->right == heap_min) { // |Roots| has one element, special case
Node *new_heap_min = heap_min->child;
_remove_parents_from_circular_list(heap_min->child);
delete heap_min;
heap_min = new_heap_min;
return;
}
Node *heap_min_children = heap_min->child;
Node *new_heap_min = heap_min->right;
// break links to other nodes on its level
_extract_from_circular_list(heap_min);
// before deleting
delete heap_min;
_remove_parents_from_circular_list(heap_min_children);
heap_min = _merge(new_heap_min, heap_min_children);
_consolidate();
}
void _cut(Node *node) {
node->mark = false; // Mark it, since it has been cut
// Break links to parent and siblings
if(node->right == node) node->parent->child = nullptr;
else node->parent->child = node->right;
node->parent->degree -= 1;
_extract_from_circular_list(node);
node->parent = nullptr;
// Add it to |Roots|
heap_min = _merge(heap_min, node);
}
void _cascut(Node *node) { // cascading cut
if(node->parent == nullptr) {
node->mark = false;
return;
}
if(node->mark == false) {
node->mark = true;
}
else {
Node *parent = node->parent;
_cut(node); _cascut(parent);
}
}
void _decrease_key(Node *node, const DATA& new_key) {
node->key = new_key;
if(node->parent == nullptr) {
if( op.less(node->key, heap_min->key) ) heap_min = node;
}
else {
Node *parent = node->parent;
_cut(node); _cascut(parent);
}
}
public:
struct Iterator {
// private:
Node *node_ptr;
// public:
Iterator() { node_ptr = nullptr; }
Iterator(Node *_node_ptr) { node_ptr = _node_ptr; }
DATA value() { return node_ptr->key; }
};
FibonacciHeap() {
heap_min = nullptr; node_count = 0;
}
void clear() { node_count = 0; _erase(heap_min); heap_min = nullptr; }
size_t size() { return node_count; }
Iterator insert(const DATA &v) {
node_count += 1;
Node *v_node = new Node(v);
heap_min = _merge(heap_min, v_node);
return Iterator(v_node);
}
DATA get_min() {
jassert(heap_min != nullptr, "heap must not be empty", heap_min);
return _get_min();
}
void pop_min() {
jassert(heap_min != nullptr, "heap must not be empty", heap_min);
node_count -= 1; _pop_min();
}
void decrease_key(Iterator it, const DATA& new_key) {
jassert( !op.less(it.value(), new_key), "New key must be less than old key", new_key, it.value());
_decrease_key(it.node_ptr, new_key);
}
void decrease_key_if_smaller(Iterator it, const DATA& new_key) {
if( op.less(new_key, it.node_ptr->key) ) _decrease_key(it.node_ptr, new_key);
}
void erase(Iterator it) {
jassert(heap_min != nullptr, "heap must not be empty", heap_min);
node_count -= 1;
_decrease_key(it.node_ptr, op.min());
_pop_min();
}
};
};
#include <bits/stdc++.h>
using namespace std;
struct data {
int dist, id;
data() { dist = id = 0; }
data(int _d, int _i) {
dist = _d; id = _i;
}
};
struct ops {
data min() { return data(-(1 << 30), -1); }
bool less(const data& a, const data& b) const { return a.dist < b.dist; }
};
using namespace ja::AdvancedDataStructures::FibonacciHeap;
#ifdef INFOARENA
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define cin in
#define cout out
#endif // INFOARENA
const int NMAX = 5e4 + 7;
vector<pair<int, int>> g[NMAX];
int dist[NMAX]; bool pushed[NMAX];
FibonacciHeap<data, ops> fibheap;
FibonacciHeap<data, ops>::Iterator it[NMAX];
const int MAXDIST = 2e9 + 7;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y, c; cin >> x >> y >> c;
g[x].push_back({y, c});
// g[y].push_back({x, c});
}
for(int i = 1; i <= n; i++) {
it[i] = fibheap.insert({MAXDIST, i});
}
fibheap.decrease_key(it[1], {0, 1});
while(fibheap.size() > 0) {
data cnt = fibheap.get_min(); fibheap.pop_min();
int node = cnt.id;
pushed[node] = true;
dist[node] = cnt.dist;
for(auto vec : g[node]) {
if(!pushed[vec.first])
fibheap.decrease_key_if_smaller(it[vec.first], {cnt.dist + vec.second, vec.first});
}
}
for(int i = 2; i <= n; i++) {
if(dist[i] == MAXDIST) dist[i] = 0;
cout << dist[i] << ' ';
}
}