#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 100000;
struct KeyValue {
	int u;
	ll dis;
	KeyValue() {
	}
	KeyValue(int u_, ll dis_) {
		u = u_;
		dis = dis_;
	}
};
bool operator < (const KeyValue & a, const KeyValue & b) {
	return a.dis < b.dis;
}
struct FibonacciHeapNode {
	KeyValue key;
	FibonacciHeapNode * child, * left, * right, * father;
	int degree;
	bool mark;
	FibonacciHeapNode(KeyValue x) {
		key = x;
		child = left = right = father = nullptr;
		degree = 0;
		mark = false;
	}
	void insert(FibonacciHeapNode * p) {
		p -> left = left;
		p -> right = this;
		left -> right = p;
		left = p;
	}
	void remove() {
		right -> left = left;
		left -> right = right;
		left = right = this;
	}
	void cut() {
		father -> degree--;
		if (left == this) {
			father -> child = nullptr;
		} else {
			if (father -> child == this) {
				father -> child = left;
			}
			remove();
		}
		father = nullptr;
	}
};
int log2(int x) {
	for (int i = 0; ; i++) {
		if (x < (1 << i)) {
			return i - 1;
		}
	}
}
void swap(FibonacciHeapNode * & a, FibonacciHeapNode * & b) {
	FibonacciHeapNode * temp = a;
	a = b;
	b = temp;
}
struct FibonacciHeap {
	FibonacciHeapNode * min, ** cons;
	int node_number;
	FibonacciHeap() {
		min = nullptr;
	}
	FibonacciHeapNode * insert(KeyValue key) {
		FibonacciHeapNode * p = new FibonacciHeapNode(key);
		if (min == nullptr) {
			min = p;
			min -> left = min -> right = min;
		} else {
			min -> insert(p);
			if (p -> key < min -> key) {
				min = p;
			}
		}
		node_number++;
		return p;
	}
	void merge(FibonacciHeap * other) {
		min -> left -> right = other -> min;
		other -> min -> left -> right = min;
		swap(min -> left, other -> min -> left);
		if (other -> min -> key < min -> key) {
			min = other -> min;
		}
		other -> min = nullptr;
		node_number += other -> node_number;
	}
	KeyValue find_min() {
		return min -> key;
	}
	void consolidate() {
		int length = log2(node_number) + 2;
		cons = new FibonacciHeapNode * [length];
		for (int i = 0; i < length; i++) {
			cons[i] = nullptr;
		}
		while (min != nullptr) {
			FibonacciHeapNode * p = min;
			if (min -> left != min) {
				min = min -> right;
				p -> remove();
			} else {
				min = nullptr;
			}
			if (cons[p -> degree] == nullptr) {
				cons[p -> degree] = p;
			} else {
				if (p -> key < cons[p -> degree] -> key) {
					swap(cons[p -> degree], p);
				}
				if (cons[p -> degree] -> child == nullptr) {
					cons[p -> degree] -> child = p;
				} else {
					cons[p -> degree] -> child -> insert(p);
				}
				cons[p -> degree] -> degree++;
				p -> father = cons[p -> degree];
				int now = p -> degree;
				while (cons[now + 1] != nullptr) {
					if (cons[now] -> key < cons[now + 1] -> key) {
						swap(cons[now], cons[now + 1]);
					}
					cons[now + 1] -> child -> insert(cons[now]);
					cons[now + 1] -> degree++;
					cons[now] -> father = cons[now + 1];
					cons[now] = nullptr;
					now++;
				}
				cons[now + 1] = cons[now];
				cons[now] = nullptr;
			}
		}
		int count = 0;
		for (int i = 0; i < length; i++) {
			if (cons[i] != nullptr) {
				cons[count] = cons[i];
				count++;
			}
		}
		for (int i = 0; i < count; i++) {
			cons[i] -> left = cons[(i - 1 + count) % count];
			cons[i] -> right = cons[(i + 1) % count];
		}
		min = cons[0];
		for (int i = 1; i < count; i++) {
			if (cons[i] -> key < min -> key) {
				min = cons[i];
			}
		}
		delete [] cons;
	}
	void extract_min() {
		if (min -> child != nullptr) {
			while (min -> child != nullptr) {
				FibonacciHeapNode * p = min -> child;
				p -> cut();
				min -> insert(p);
			}
		}
		if (node_number == 1) {
			min = nullptr;
		} else {
			FibonacciHeapNode * p = min -> right;
			min -> remove();
			delete min;
			min = p;
		}
		node_number--;
		if (node_number >= 1) {
			consolidate();
		}
	}
	void cascading_cut(FibonacciHeapNode * p) {
		if (p -> mark) {
			p -> cut();
			cascading_cut(p -> father);
			min -> insert(p);
			p -> father = nullptr;
			p -> mark = false;
		} else if (p -> father != nullptr) {
			p -> mark = true;
		}
	}
	void decrease_key(FibonacciHeapNode * p, KeyValue new_key) {
		if (p -> key < new_key) {
			printf("Error The new key is greater than current key.\n");
			return;
		}
		p -> key = new_key;
		if (p -> father != nullptr && new_key < p -> father -> key) {
			cascading_cut(p -> father);
			p -> cut();
			min -> insert(p);
			p -> mark = false;
		}
		if (p -> key < min -> key) {
			min = p;
		}
	}
	void delete_node(FibonacciHeapNode * p) {
		decrease_key(p, KeyValue(p -> key.u, -2147483647 - 1));
		extract_min();
	}
};
struct Edge {
	int v;
	ll w;
	Edge() {
	}
	Edge(int v_, ll w_) {
		v = v_;
		w = w_;
	}
};
vector < Edge > edge[N];
ll dis[N];
FibonacciHeapNode * node[N];
FibonacciHeap heap;
int main() {
	int n, m;
	scanf("%d %d %*d", &n, &m);
	for (int u, v, w, i = 1; i <= m; i++) {
		scanf("%d %d %d", &u, &v, &w);
		u--;
		v--;
		edge[u].push_back(Edge(v, w));
	}
	for (int u = 0; u < n; u++) {
		dis[u] = 0x3f3f3f3f3f3f3f3f;
	}
	dis[0] = 0;
	for (int i = 0; i < n; i++) {
		node[i] = heap.insert(KeyValue(i, dis[i]));
	}
	for (int u, i = 0; i < n; i++) {
		u = heap.find_min().u;
		node[u] = nullptr;
		heap.extract_min();
		for (Edge to : edge[u]) {
			if (dis[to.v] > dis[u] + to.w) {
				dis[to.v] = dis[u] + to.w;
				heap.decrease_key(node[to.v], KeyValue(to.v, dis[to.v]));
			}
		}
	}
	for (int i = 0; i < n; i++) {
		printf("%lld ", dis[i]);
	}
	return 0;
}