P13081 [NOISG 2017] Roadside Advertisements / 广告投放

译自 [NOISG 2017 B.Roadside Advertisements](https://github.com/noisg/sg_noi_archive/tree/master/2017/roadsideadverts)。 ------------ NOISG2017 拥有 $5$ 个赞助商。

新加坡的地图可以视为一张 $V$ 个点 $V-1$ 条边的图，其中点的编号为 $0,1,\cdots V-1$。保证任意两点间有且仅有唯一路径。 已知 $5$ 个赞助商分别位于 $a,b,c,d,e$ 号点，NOISG 主席 TAN Sun-Teck 想要在一些边上投放广告，使得 $5$ 个赞助商两两间最短路径上的每一条边都投放了广告。 对于每条边，在该边上投放广告的成本是已知的。投放广告的总成本是每条需投放广告的道路成本的总和。$Q$ 次询问，每次给定 $a,b,c,d,e$，求满足要求的最低总成本。

第一行一个正整数 $V$。 接下来 $V−1$ 行，每行三个整数 $u,v,w$，表示 $u$ 号点和 $v$ 号点间有一条道路相连，并且在这条道路上投放广告需要 $w$ 新加坡元。 接下来一行包含一个正整数 $Q$，表示询问次数。 接下来 $Q$ 行，每行五个整数 $a,b,c,d,e$，表示 $5$ 个赞助商的位置。保证 $a,b,c,d,e$ 两两不同。

对于每次询问，一行一个整数表示投放广告的最低总成本。

### 【样例 2 解释】  对于第一次询问，$5$ 个赞助商分别位于 $4,0,3,5,2$ 号点（请注意编号不一定按升序排列）。易知我们需要在每一条路边投放广告，最低成本是所有道路的成本之和，即 $4+2+9+1+5=21$。 对于第二次询问，$5$ 个赞助商位于 $0,4,1,3,5$ 号点。这一次我们不需要在 $(3,2)$ 这条道路上投放广告。因此总成本为 $21−5=16$。 ### 【数据范围】 **本题采用 $\text{Subtask}$ 捆绑测试。** |$\text{Subtask}$|分值|$V,Q$ 的范围|特殊性质| |:-:|:-:|:-:|:-:| |$1$|$7$|$V=5,Q=1$|无| |$2$|$23$|$5\le V\le5\times10^4,1\le Q\le 10^4$|有| |$3$|$40$|$5\le V\le5\times10^4,1\le Q\le 100$|无| |$4$|$30$|$5\le V\le5\times10^4,1\le Q\le 10^4$|无| 特殊性质：保证每个点最多与 $2$ 个点间有道路相连。 对于所有数据，保证 $5\le V\le5\times10^4$，$1\le Q\le 10^4$，$0\le u,v