1218 : 宝石交易

Description

最近小Y沉迷宝石鉴赏，他在宝石流通市场淘货，小Y很快就与一些宝石商人建立起来了友谊，这些宝石商人只接受以物换物，即一颗宝石交换一颗宝石，如果宝石不同的话可能需要补贴差价，现在这些商人给出了\(m\)种宝石交易规则，对于第 \(i\) 种宝石，可以花费 \(c_i\) 的差价将宝石 \(a_i\) 变成宝石 \(b_i\)，需要注意的是，由于宝石的稀有性，反过来的交易规则可能不会被宝石商人们所接受 。

情人节快到了，小Y淘到了两条长度均为 \(n\) 的宝石项链（项链上的宝石首尾相接构成环），她想要跟这些商人交换项链上的宝石，将两条链条的相同位置的宝石都变得相同。需要注意的是，小Y只会选择两条项链的起点后，沿着同一方向（均为顺时针或者均为逆时针）逐一进行宝石交易，由于可能会存在多种变化的方式，小Y想知道如果选择的位置合适的话，最少要补贴多少差价。如果不存在使得两条项链变得相同的方法就输出 \(-1\) 。

Input

第一行输入两个数 \(n\) ，\(m\) 。

接下来 \(1\) 行， \(n\) 个数 \(s_1,\ ...\ ,s_n\) 表示第一条链条从左到右宝石的种类。

接下来 \(1\) 行， \(n\) 个数 \(t_1,\ ...\ ,t_n\) 表示第二条链条从左到右宝石的种类。

接下来 \(m\) 行，每行三个数 \(a_i\) , \(b_i\) , \(c_i\)，含义与题目描述一致，可能存在多个将 \(a_i\) 变为 \(b_i\) 的巫术。

对于 \(100\%\) 的数据， \(1 \leq n \leq 10^4\), \(1 \leq m \leq 10^5\), \(1 \leq a_i, b_i \leq 400\), \(1 \leq c_i \leq 100\);

Output

输出一行，一个整数表示最少的补贴差价。如果不存在使得两条链条变得相同的方法就输出 \(-1\) 。

Sample

4 3
1 2 3 4
1 5 5 4
2 5 8
5 3 13
4 6 3

21

Hint

我们使用 \(8\) 的魔力值，将第一条宝石项链中的 \(2\) 颜色变成 \(5\) 颜色；再使用 \(13\) 的魔力值，将第二条宝石项链中的 \(5\) 颜色变成 \(3\) 颜色，这样两个项链的颜色都变成了 \(1,5,3,4\)，花费了 \(21\) 魔力值，并且可以证明这个是魔力值最小的方案。

Source