4737: b宝石交易

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

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

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

接下来 1 行， n 个数 s1, ... ,sn 表示第一条链条从左到右宝石的种类。

接下来 1 行， n 个数 t1, ... ,tn 表示第二条链条从左到右宝石的种类。

接下来 m 行，每行三个数 ai , bi , ci，含义与题目描述一致，可能存在多个将 ai 变为 bi 的巫术。

对于 100% 的数据， 1≤n≤104, 1≤m≤105, 1≤ai,bi≤400, 1≤ci≤100;

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

21