#pragma GCC optimize("Ofast")
#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;

			_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] << ' ';
    }
}