CSG-CPC
Online Judge

1218 : 宝石交易

         Time Limit: 1 Sec     Memory Limit: 256 Mb     Submitted: 11     Solved: 2    

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\) 魔力值,并且可以证明这个是魔力值最小的方案。