热爱旅行的小苯生活在 国， 国可以看做是一个由 座城市，编号从 到 ，和恰好 条双向道路连接起来的连通图。 这天他要招待远道而来的 个朋友，帮助他们设计一个旅行计划，使得所有人的总花费最小。 具体的：每个朋友都有一个旅行计划，一共有 个旅行计划，其中第 个朋友的旅行计划是从城市 沿最短路一路旅行至城市 。 但每个人通过每条道路都要交一定的过路费，小苯作为朋友们的“导游”，至多可以想办法使得一条道路免费，即任何人通过它任意次都不花钱。 现在小苯希望你帮他找到那个使得其免费后就能让所有朋友的总花费最小的道路，并告诉他这个最小的总花费吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：第一行输入两个正整数 ，分别表示 国的城市数量，和小苯的朋友个数。接下来 行，每行三个正整数 ，表示 国的一条双向道路，连接 这两座城市，任何人通过一次它的花费是 。接下来的 行，每行两个正整数 ，分别表示每个朋友的旅行计划。（保证同一个测试文件的所有测试数据中， 的总和不超过 ， 的总和不超过 。）

输出描述:

对于每组测试数据，在单独的一行输出一个整数 ，表示最小的总花费。（数据保证答案不超过 。）