在一座城市里有 n 个快递点,快递点之间由 n-1 条双向边联通。保证图的结构随机。
现在有 q 个运输任务,第 i 个运输任务要求把重量为 w_i 的货物从 u_i 运输 v_i 。每个任务会给从 u_i 到 v_i 的路径上(包含 u_i,v_i )的每个点增加 w_i 的运输压力。
请输出运输压力最大的点的压力是多少。
输入共 n+q 行。
第一行两个以空格隔开的正整数 n,q 。
从第二行开始的 n-1 行,每行两个正整数 p_i,q_i ,表示 p_i 和 q_i 之间有一条双向边。
从第 n+1 行开始的 q 行,每行 3 个整数 u_i,v_i,w_i ,第 n+i 行代表从 u_i 运输重量为 w_i 的货物到 v_i 。
输出一行一个整数,运输压力最大的点的压力。
3 11 21 32 3 2
2
7 21 21 32 42 52 63 74 5 26 3 5
7
对 30\% 的数据, 1\le n\le 10 。
对 60\% 的数据, 1\le n\le 1000 。
对所有的数据 1\le n\le 100000 , 1\le u_i,v_i\le n , 1\le q\le 100000 , 0\le w_i\le 1000 。