坐落在 Bzeroth 大陆上的精灵王国击退地灾军团的入侵后，经过十余年的休养生息，重新成为了一片欣欣向荣的乐土，吸引着八方游客。小 W 是一位游历过世界各地的著名美食家，现在也慕名来到了精灵王国。
精灵王国共有 n 座城市，城市从 1 到 n 编号，其中城市 i 的美食能为小 W 提供 c_n 的愉悦值。精灵王国的城市通过 m 条单向道路连接，道路从 1 到 m 编号，其中道路 i 的起点为城市 u_i，终点为城市 v_i，沿它通行需要花费 w_i 天。也就是说，若小 W 在第 d 天从城市 u_i 沿道路 i 花费 w_i 天到达城市 v_i 。
小 W 计划在精灵王国进行一场为期 T 天的旅行，更具体地：他会在第 0 天从城市 1 出发，经过 T 天的旅行，最终在恰好第 T 天回到城市 1 结束旅行。由于小 W 是一位美食家，每当他到达一座城市时（包括第 0 天和第 T 天的城市 1），他都会品尝该城市的美食并获得其所提供的愉悦值，若小 W 多次到达同一座城市，他将获得多次愉悦值。注意旅行途中小 W 不能在任何城市停留，即当他到达一座城市且还未结束旅行时，他当天必须立即从该城市出发前往其他城市。
上图为样例1对应的图，此时没有美食节，小 W 一种为期 11 天的可行旅游方案为 1→2→1→2→3→1：
第 0 天，小 W 从城市 1 开始旅行，获得愉悦值 1 并向城市 2 出发。
第 1 天，小 W 到达城市 2，获得愉悦值 3 并向城市 1 出发。
第 4 天，小 W 到达城市 1，获得愉悦值 1 并向城市 2 出发。
第 5 天，小 W 到达城市 2，获得愉悦值 3 并向城市 3 出发。
第 7 天，小 W 到达城市 3，获得愉悦值 4 并向城市 11 出发。
第 11 天，小 W 到达城市 1，获得愉悦值 1 并结束旅行。
小 W 在该旅行中获得的愉悦值之和为 13。
此外，精灵王国会在不同的时间举办 k 次美食节。具体来说，第 i 次美食节将于第 t_i 天在城市 x_i 举办，若小 W 第 t_i 天时恰好在城市 x_i ，那么他在品尝城市 x_i 的美食时会额外得到 y_i 的愉悦值。
现在小 W 想请作为精灵王国接待使者的你帮他算出，他在旅行中能获得的愉悦值之和的最大值。