本题是单源最短路径的模板题，使用堆优化的 $\rm {Dijkstra}$ 算法即可通过。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

using i64 = long long;
const int MAXN = 100005;
const i64 INF = 1e18;

struct Edge {
	int v, w;
};

vector<Edge> e[MAXN];
i64 dis[MAXN]; 
bool vis[MAXN];

struct Point {
	int p;
	i64 w;
};

struct cmp {
	bool operator()(Point &a, Point &b) {
		return a.w > b.w; 
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, s;
	cin >> n >> m >> s;
	
	while (m--) {    
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back(Edge{v, w});
	}
	
	fill(dis, dis + n + 1, INF); 
	priority_queue<Point, vector<Point>, cmp> q; 
	q.push(Point{s, 0}); 
	dis[s] = 0;
	while (!q.empty()) {
		Point head = q.top();
		q.pop();
		int now = head.p;
		if (vis[now]) continue; 
		vis[now] = true;
		for (int i = 0; i < e[now].size(); i++) {
			int v = e[now][i].v;
			int w = e[now][i].w;
			if (dis[now] + w < dis[v]) {
				dis[v] = dis[now] + w;
				q.push(Point{v, dis[v]});
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		if (dis[i] == INF) cout << -1 << ' ';
		else cout << dis[i] << ' ';
	}
	
	return 0;
}