AC（Dijkstra）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii; // (距离, 节点)

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	// 构建图的邻接表，节点编号从1到n
	vector<vector<pii>> graph(n + 1);

	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].push_back({v, w}); // 有向边 u->v，权重为w
	}

	// 初始化距离数组，dist[i]表示从1到i的最短距离
	vector<ll> dist(n + 1, LLONG_MAX);
	dist[1] = 0; // 起点到自己的距离为0

	// 使用最小堆来存储待处理的节点
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, 1}); // (距离, 节点)

	while (!pq.empty()) {
		ll cur_dist = pq.top().first;
		ll cur_node = pq.top().second;
		pq.pop();

		// 如果当前距离大于已知最短距离，跳过
		if (cur_dist > dist[cur_node]) {
			continue;
		}

		// 遍历当前节点的所有邻居
		for (auto &edge : graph[cur_node]) {
			ll next = edge.first;
			ll weight = edge.second;

			// 计算通过当前节点到达邻居节点的距离
			ll new_dist = cur_dist + weight;

			// 如果找到更短的路径，则更新距离并加入优先队列
			if (new_dist < dist[next]) {
				dist[next] = new_dist;
				pq.push({new_dist, next});
			}
		}
	}

	// 输出结果
	for (int i = 1; i <= n; i++) {
		if (dist[i] == LLONG_MAX) {
			cout << -1 << " "; // 不可达
		} else {
			cout << dist[i] << " ";
		}
	}

	return 0;
}