typedef long long ll;
struct edge{
	int v;
	ll w;
	edge(int vv,ll ww) {
		v = vv;
		w = ww;
		return;
	}
};
struct node{
	int id;
	ll dis;
	node(int idd,ll diss) {
		id = idd;
		diss = dis;
		return;
	}
	bool operator<(node xx) const{//小根堆 
		return dis > xx.dis;
	}
};
int n,m,s;
vector<edge> g[100010];
ll dis[100010];
bool vis[100010];
priority_queue<node> q;
void Dijkstra() {
	memset(dis,0x7f,sizeof(dis));
	dis[s] = 0;
	q.push(node(s,0));
	while (!q.empty()) {
		node u = q.top();
		q.pop();
		if (vis[u.id]) continue;//
		vis[u.id] = true;//
		for (int i = 0;i < g[u.id].size();i ++) {
			int v = g[u.id][i].v;
			ll w = g[u.id][i].w;
			if (dis[v] > u.dis + w) {
				dis[v] = u.dis + w;
				q.push(node(v,dis[v]));
			}
		}
	}
	return;
}