迈尔斯的逃亡

时间限制： 4 秒
内存限制： 256 MB
输入： 标准输入
输出： 标准输出

题目描述

迈尔斯又一次从米格尔·奥哈拉手中逃脱，但这次他带上了能在两个世界之间穿梭的设备。不幸的是，他的移动仅限于每个世界中的一个城市。不过这两个城市非常相似：每个城市都有恰好 $n$ 座摩天楼，且它们位于空间中的相同位置。

某些位于同一世界的摩天楼对之间可以拉出蛛丝并在两者间双向移动。第一世界有恰好 $m_1$ 对这样的摩天楼，第二世界有恰好 $m_2$ 对。已知在每个世界中，在可用摩天楼对之间移动所需的时间。除此之外，迈尔斯可以从第一世界的第 $i$ 座摩天楼移动到第二世界的第 $i$ 座摩天楼，反之亦然，花费 $x$ 秒。

迈尔斯计划在第二世界的第 $t$ 座摩天楼与他的团队会合，而他开始时正在第一世界的第 $s$ 座摩天楼上。请帮助迈尔斯，告诉他最快需要多长时间才能与团队会合，从而有足够的机会对抗米格尔。

输入格式

第一行包含两个整数 $n$ 和 $x$——每个世界中的摩天楼数量，以及在不同世界的对应摩天楼之间移动的时间（$1 \le n \le 10^5$；$1 \le x \le 10^6$）。

第二行包含一个整数 $m_1$——第一世界城市中可移动的摩天楼对的数量（$0 \le m_1 \le 10^6$）。

接下来的 $m_1$ 行每行包含三个整数 $u_i$、$v_i$ 和 $c_i$，表示在第一世界中可以在摩天楼 $u_i$ 和 $v_i$ 之间双向移动，花费 $c_i$ 秒（$1 \le u_i, v_i \le n$；$1 \le c_i \le 10^6$）。

接下来的行以相同格式包含第二世界中可能移动的信息：第一行给出 $m_2$，接下来 $m_2$ 行包含移动的描述（三个整数 $u_i$、$v_i$ 和 $c_i$）。

最后一行包含两个整数 $s$ 和 $t$——第一世界中的起点摩天楼编号和第二世界中的终点摩天楼编号（$1 \le s, t \le n$）。

输出格式

输出一个整数——从第一世界的摩天楼 $s$ 到第二世界的摩天楼 $t$ 的最短旅行时间，如果不存在路径则输出 -1。

样例

输入

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

输出

6