杰杰是魔法界的一名传奇人物。他对魔法具有深刻的洞察力,惊人的领悟力,以及令人叹为观止的创造力。自从他从事魔法竞赛以来,短短几年时间,就已经成为世界公认的实力最强的魔法选手之一。更让人惊叹的是,他几乎没有借助外界力量,完全凭借自己的努力达到了普通人难以企及的高度。在最近的世界魔法奥林匹克竞赛上,他使用高超的魔法本领,一路过关斩将,在最后时刻一举击败了前冠军“旅行者”,获得了魔法界最高的荣耀:女神奖杯!女神奖杯可不是一个普通的奖杯,她能够帮杰杰实现一个愿望。
杰杰本着实事求是的态度,审时度势,向女神奖杯提出了自己的愿望:想要一个女性朋友。
杰杰的愿望实现了,可是女性朋友却和他不在一个城市。杰杰想要知道:如果要到达女性朋友的所在城市,有多少种方案供他选择?
杰杰所在的世界有n个城市,从1到n进行编号。任意两个城市都通过有向道路连接。每个城市u有k个入点权:in[u][1],in[u][2]...in[u][k],有k个出点权:ou[u][1],ou[u][2]...ou[u][k]。对于任意两个城市(u,v)(u可以等于v),u到v的道路条数为(ou[u][1]*in[v][1]+ou[u][2]*in[v][2]+...+ou[u][k]*in[v][k])条。杰杰有m次询问,每次询问由三元组(u,v,d)构成,询问从u城市通过不超过d条道路到达v城市的方案数。
为了温柔的杰杰和他的女性朋友的美好未来,帮助他解答这个问题吧。