#include<iostream>
#include<queue>
using namespace std;

class edge
{
public:
	int cost;
	int VerAdj;
	edge* link;
	edge(int v, int w) :VerAdj(v), cost(w), link(nullptr) {}
	
};
class Vertex
{
public:
	int Ver;
	int dist;
	edge* adjecent;
	Vertex() :Ver(0), dist(INT32_MAX), adjecent(nullptr) {}


	bool operator<(const Vertex& rhs) const { return dist > rhs.dist; }
	bool operator>(const Vertex& rhs) const { return dist < rhs.dist; }
};
void Dijskra(Vertex* Head, const int& s, const int &n)
{
	int* path = new int[n + 1];
	int* visited = new int[n + 1];
	priority_queue<Vertex> Q;
	for (int i = 1; i <= n; i++)
	{
		path[i] = -1; Head[i].Ver = i;
		visited[i] = 0;
	}
	Q.push(Head[s]); 
	while (!Q.empty())
	{
		int u = Q.top().Ver;
		Q.pop();
		visited[u] = 1;
		for (edge* p = Head[u].adjecent; p; p = p->link)
		{
			int v = p->VerAdj;
			if (visited[v] == 0 && Head[u].dist + p->cost < Head[v].dist)
			{
				Head[v].dist = Head[u].dist + p->cost;
				path[v] = u; Q.push(Head[v]);
			}
		}
	}

	//打印
	for (int i = 1; i <= n; i++)
	{
		cout << Head[i].dist << ' ';
	}
}
int main()
{
	int n, m, s;
	int u, v, w;
	cin >> n >> m >> s;
	Vertex* Head = new Vertex[n + 1];

	for (int i = 1; i <= m; i++)
	{
		cin >> u >> v >> w;
		edge* temp = new edge(v, w);
		temp->link = Head[u].adjecent;
		Head[u].adjecent = temp;
	}
	Head[s].dist = 0;
	Dijskra(Head, s, n);
}

堆优化，但是有两个点超时了，有大佬帮忙看一下吗