题目内容

物流公司每天都要处理很多物流的运输工作，整个城市共有 N 个地点，共有 N-1 条公路，每2个地点之间都能通过公路连通。物流公司总部位于1号地点。

今天有一辆物流运输车共有 M 条物流运输任务，物流运输车每天的工作流程如下：

先要从总部出发去收取所有的寄件货物，收到所有货物后回到总部扫描货物，再从总部出发将货物送至所有的送件地址，送完后最终回到总部，算作完成了今天的运输工作。

请问该物流运输车今天最少行驶多少路程可以完成今天的运输工作，运输任务不分先后。

输入描述

对于每组数据，第一行有2个整数，依次为 N (3 <= N <= 10^5) , M (1 <= M <= 10^5) ，表示有 N 个地点和 M 条物流任务，数字用空格分开。

接下来有 N-1 行，每行有3个整数，依次为 u(1 <= u <= N) , v(1 <= v <= N) , c(1 <= c <= 10^5) 表示从 u 到 v 有一条公路，公路里程为 c ，输入保证所有地点连通。

接下来有 M 行，每行有2个整数，依次为 s(2 <= s <= N) , t(2 <= t <= N, s ≠ t) 表示寄件任务从 s 寄到 t

输出描述

输出一个整数，表示该辆物流运输车最少行驶多少路程能够完成今天的运输工作。

样例1

输入

4 2
2 1 1
1 3 2
4 3 2
3 2
4 2

输出

10

说明

运输车从地点1开到地点3接收任务1物品，再开到地点4接收任务2物品，回到总部1扫描，扫描后将任务1和任务2的物品送到地点2，最终回到总部1，总共行驶里程10。

样例2

输入

5 2
2 1 1
1 3 2
4 3 2
1 5 3
4 2
5 4

输出

24

说明

运输车从地点1开到地点6接收任务2物品，再开到地点4接收任务1物品，回到总部1扫描，扫描后将开到地点4完成任务2，再开到地点2完成任务1，最终回到总部1，总共行驶里程24。