正所周知，一个求助帖需要一张头图 题目链接 70分

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int N = 9000 + 5;
constexpr int INF = INT_MAX;
int n , m ,s, d[N],e[N][N];
bool used[N];
void dis(int s)
{
	for(int i = 1 ; i <= n ; i++)
	{
		d[i] = INF;
	}
	d[s] = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		int mi = INF, u = -1;
		for(int v = 1 ; v <= n ; v++){
			if(!used[v] && d[v] < mi)
			{
				mi = d[v];
				u = v;
			}
		}
		if(u == -1)
		{
			break;
		}
		used[u] = true;
		for(int v = 1 ; v <= n ; v++)
		{
			if(d[u] != INF && e[u][v] != INF && d[v] > d[u] + e[u][v]) d[v] = d[u] + e[u][v];
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	for(int i = 1 ; i <=  n ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			e[i][j] = INF;
		}
		e[i][i] = 0 ;
	}
	for(int i = 0 ; i < m ; i++)
	{
		int u , v , w;
		cin >> u >> v >> w;
		e[u][v] = min(e[u][v],w);
	}
	dis(s);
	for(int i = 1 ; i <= n ; i++)
	{
		if(d[i] == -1) d[i] = INF;
		cout << d[i] << " " ;
	}
}