U278715 【MOVE0019】聚会

此题为本人搜集，有版权问题，请联系。

小明、小亮和小强三人是好朋友，他们喜欢游玩的地点总共有n 个，这n 个地点由有 N-1 条长度均为1 千米的道路连接。他们三人经常组织聚会，想请你为他们选择一个地点， 使得三个人到达这个地点的总路程最小。

第一行两个正整数，n 和m。表示游玩地点的个数和聚会次数，游玩地点的编号为1~n； 后面有n-1 行，每行用两个正整数u 和v 表示一条道路连接的两个地点的编号； 再后面有m 行，每行用三个正整数表示一次聚会的情况：即三人当前所在地点的编号。

一共有m 行，每行两个数p 和c，用一个空格隔开。表示第i 次聚会的地点选择在 编号为p 的地点，三个人到达这个地点的总路程取得最小值c。

对于40%数据，$1 ≤ n, m ≤ 2000$； 对于全部数据，$1 ≤ n, m ≤ 5×10^5$。