U318482 文件传输

C.P.（$1$号）想要把一个$K$MB的，压缩后是$k$MB的文件传输给酷町问答的一名大佬X（$n$号）。但是C.P.没有X的QQ或微信以及线下联系方式。于是C.P.在问答上找了$n$名同学$(n\leqslant 10^4)$，并且其中$m$对同学有单向或双向的文件传输方式$(m\leqslant 10^5)$，不同的同学之间文件传输速度不同，甚至正反方向也会影响。为了加快速度，这些同学都可以压缩或解压缩文件，但是每个同学压缩或解压缩时间都不一样。C.P.想知道最快要花多长时间。

输入共$m+3$行。 第一行共$4$个数字，分别是$n,m,K,k$。 第二、三行共$n$个数字，代表每名同学压缩、解压缩该文件的时间。（单位：分钟） 接下来$m$行，每行$3$个数字，分别代表发文件的同学，收文件的同学和传输速度（每MB几分钟）

输出仅一行，表示最短时间。（单位：分钟）

1->2，10分钟 2压缩，2分钟 2->4，3分钟 4解压，3分钟 4->5，20分钟 共38分钟 传输速度不超过$10^3$分钟$^{-1} $MB，文件大小不超过$10^3$MB，（解）压缩时间不超过$10^3$分钟