题目背景

面基完毕后已经是晚上了，IY 和 SY在机房划水写板子。

然后机房跳闸了。

然后他们核善的信息老师叫他们修闸。

IY 和 SY 迫于威胁不得不修闸。

于是有了下面这一幕。

题目描述

IY 和 SY 发现总闸的电路已经完全损坏了，于是他们不得不重新设置一个电路。

机房里有 $n$ 个电流传导节点，每个节点可以用电线连向其他节点。相通的节点可以互相传递电流。

由于预留空间的问题，导致有些节点是不能直接连接的。现在 IY 和 SY 知道有 $m$ 组节点可以直接连接，并且知道连接这一组节点需要的电线长度。

光有电流传导节点肯定不行。SY 掏出了她珍藏已久的电源发生器。电源发生器可以附着在结点上，给那个节点供电。但是电源发生器也有一些缺陷，它只能附着在 $s$ 号节点上，且只有 $k$ 个接口，也就是说附着的节点只能连 $k$ 条电线，而且由于联动原因，只有发生器所有的接口都连上电线，发生器才会供电。

IY 和 SY 的目标是让所有节点都可以被供电。他们需要电线，然而电线越长，其价格就以指数倍增长。所以他们都想让最长的电线尽量短。

SY 接下了铺设电线的任务，IY 则被分配去买电线，他需要知道他总共要买多长的电线。由于 SY 忙于铺设电路，所以 IY 还要回答 SY 的每个询问：让 $u$ 结点和 $v$ 结点相通所需要的电线的总长度为多少。但是 IY 太弱了，他根本不知道这些答案是多少。

请你帮助弱弱的 IY 回答这些问题。作为奖励，这道题他会给你满分哦。

输入格式

第一行四个数$n,m,k,s$，表示有$n$个节点，$m$组可以直接连接的节点，电源发生器有$k$个接口，电源发生器附着在 $s$ 节点上。

下面的 $m$ 行，每行三个数 $u,v,w$，表示 $u$ 和 $v$ 节点可以用电线直接相连，在这两个节点之间铺设电线，需要的电线长度为 $w$ 。

再下面一行有一个数 $q$，表示 SY 有 $q$ 个询问。

下面的 $q$ 行每行两个数 $u,v$，表示 SY 询问 IY ： 让$u$ 结点和 $v$ 结点相通需要多长的电线。

输出格式

第一行输出一个数，代表所有电线的总长度。

下面的 $q$ 行，每行一个数，表示对 SY 每个询问的回答。

可能存在无解的情况，如果无解，则输出"can not fix it."，然后什么都不要输出。

5 7 1 1
1 3 1
2 1 5
4 2 3
2 5 4
5 1 2
3 5 7
4 1 6
2
3 5
1 4

15
7
15

提示

• 样例解释

如图，发生器附着在节点$1$上且只能连一条电线，其中红线表示连的电线，可以看出这样连是最优的。

• 数据范围

对于$30\%$ 的数据：$n \le 10, m \le 30, q \le 10$

对于$50\%$ 的数据：$n \le 2000, m \le 20000, q \le 2000$

对于$100\%$ 的数据：$n \le 30000, m \le 500000, q \le 30000, 1 \le s \le n, 1 \le k \le 150$

对于$100\%$ 的数据：满足连接两组不同的节点所需电线长度不同（即边权全部不相等），保证运算过程中不会爆$int$

• 出题人的温馨提醒

题目要满足最长的电线尽量短，在此基础上还要满足次长的电线尽量短，以此类推。

不保证没有重边，但是保证边数足够，不会选择重边。

保证没有自环，保证数据全随机。