Gem Knight（宝石骑士），宝石骑士很喜欢宝石，他结识一些宝石商人，这些宝石商人只接受以物换物，即一颗宝石交换一颗宝石，因为宝石在每个地区的稀有度不同所以宝石不同的话可能需要补贴差价，现在这些商人给出了 m 种宝石交易规则，对于第 i 种宝石，可以花费 c_i 的差价将宝石 a_i 变成宝石 b_i ，也可以将宝石 b_i 变为宝石 a_i。 宝石骑士做了两条长度均为 n 的宝石项链（项链上的宝石首尾相接构成环），他想要跟这些商人交换项链上的宝石，将两条链条的相同位置的宝石都变得相同。需要注意的是，宝石骑士只会选择两条项链的起点后，沿着同一方向（均为顺时针或者均为逆时针）逐一进行宝石交易，由于可能会存在多种变化的方式，宝石骑士想知道如果选择的位置合适的话，最少要补贴多少差价。如果不存在使得两条项链变得相同的方法 就输出 -1。

第一行输入两个整数 n, m.
接下来 1 行，n 个数 s₁, ..., s_n 表示第一条链条从左到右宝石的种类。
接下来 1 行，n 个数 t₁，...,t_n 表示第二条链条从左到右宝石的种类。
接下来 m 行， 每行三个数 a_i, b_i, c_i，含义与题目描述一致，可能存在多个将 a_i 变为 b_i 的交易方式。

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

样例说明，补贴 8 差价将第一条项链中的 2 颜色变为 5 颜色；再补贴 13 差价，将第二条项链的 5 颜色变成 3 颜色，这样这两条项链都变成了 1，5，3，4，花费 21。
数据范围：
1 <= n <= 10⁴
1 <= m <= 10⁵
1 <= a_i, bi , s_i , t_i <= 400
1 <= c_i <= 100

 第一届讯飞杯复赛 图论