给定一张 个结点, 条无向边的无向图,每条边长度为 。每个结点带有黑色或白色中的一种颜色。规定一条路径从起点出发后任意时刻白色结点的数量减黑色结点的数量大于 ,或者黑色结点的数量减白色结点的数量大于 则路径非法。问从 点到 点的所有合法路径中的最短路径长度是多少。
第一行四个正整数 , , , ,含义在题目描述中给出。
接下来一行有 个整数, 表示白色, 表示黑色。
接下来 行,每行三个数 , , 表示 点与 点之间存在一条长度为 的无向边。
最后一行两个正整数 , ,表示路径的起点和终点。
输出一行整数 ,表示最短路长度。如果路径不存在输出 。
2 1 1 1 1 1 1 2 1 1 2
-1
2 1 2 1 1 1 1 2 1 1 2
1