题解

题目描述

物流公司总部位于编号为 $1$ 的地点，城市共有 $N$ 个地点、$N-1$ 条连通所有地点的公路。今天有 $M$ 条寄送任务，每条任务都由一个寄件地 $s$ 和一个收件地 $t$（均在 $2\le s,t\le N$，且 $s\neq t$）组成。

运输车工作流程分两阶段：

1. 收件阶段：从总部（$1$）出发，按任意顺序跑到所有寄件地点 $\{s_i\}$，收取货物后回到总部（$1$）扫描。
2. 送件阶段：从总部（$1$）出发，按任意顺序将扫描后的货物送到所有送件地点 $\{t_i\}$，送完后回总部（$1$）。

题目内容

物流公司每天都要处理很多物流的运输工作，整个城市共有$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),(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$开到地点$5$接收任务$2$物品，再开到地点$4$接收任务$1$物品，回到总部$1$扫描，扫描后将开到地点$4$完成任务$2$，再开到地点$2$完成任务$1$，最终回到总部$1$，总共行驶里程$24$