众所周知，企鹅物流是龙门的一家正经的物流运输公司。
龙门一共有 家住户，这 家住户通过 条道路连接形成一个无向图 。
正值愚人节这几天，企鹅物流的老板 大帝为了庆祝他的演唱会顺利进行，准备每天给龙门的每一位住户发放企鹅物流的精美小礼品，这可把德克萨斯愁坏了，这么多的礼物怎么送的完。
但是幸运的是，龙门这几天开交通管制，每条边有一个权值 , 只有重量 的货可以通过。这可把德克萨斯高兴坏了，这下子他可以摸鱼了。
龙门人非常的慷慨，虽然是免费送的小礼品，但是他们会回报 的小费，德克萨斯想得到尽可能多的小费。
总的来说，一共有 天要送货，每天从点 出发开始送重量为 的货，只能经过 的边，经过一个点就可以得到 的小费，问每天最多能得到多少小费。