题目描述Description

动森王国由 n-1 条铁路将 n 个城市连城一片，每条铁路每天双向客运总量有一个上限，全国的需求订单由i23ob统一处理.

每天都会有很多小朋友想要组团从a地前往b地游玩，需要从i23ob订票，能够成团前往的前提是订票时刻从a地到b地的最短路线上所有铁路当天剩余客运量都能够容纳该订单的小朋友人数.

i23ob按顺序处理订单，成行的订单会对应扣除每段铁路当天的剩余客运量相应的成团人数.

按顺序给出一天的订单，计算有多少小朋友开心地成行了.

输入格式Input

不超过 10 组测试数据，每组数据第一行为两个整数 n m，表示有 n 个城市，这一天有 m 个订单.

接下来 n-1 行，每行三个整数 u v w 表示 u、v之间有一条直达铁路，双向客运总量为 w.

之后有 m 行按顺序给出订单需求，每行三个整数 a b k 表示有k个小朋友想要成团从a地出发到b地游玩.

数据范围：

• 1 \leq n, m, w, k \leq 40000
• 1 \leq u < v \leq n
• 1 \leq a < b \leq n

输出格式Output

每组数据输出一个整数，这一天成行的小朋友个数。

样例Sample

出题Author

CSGrandeur

来源Source

湖南省第十八届大学生计算机程序设计竞赛（HNCPC2022）