为了奖励奶牛们的辛勤工作，FJ决定带他的奶牛们到大城市参观。奶牛们要自己决定如何最好的度过美好的旅行时光。

幸运的是，她们有一张详细的城市地图，显示了大城市中的N(2≤L≤1000)个景点，编号为1...N，和M（2≤M_i≤5000）条连接景点的单向牛道。FJ会把奶牛们带到她们选择的起始景点，并在那里等待她们。奶牛们将会从起始景点开始沿着奶牛小道参观一系列的其他景点，最后回到起始景点，FJ会从那里将她们接回农场。由于城市中空间非常宝贵，因此奶牛小道非常的狭窄，因此只能沿着一个方向走。

尽管奶牛们可能会在城市中度过尽可能多的时间，但她们实在是很容易变得无聊。参观新的景点会很有趣，但是从一个景点走到另一个景点却很痛苦。奶牛们知道每个景点的趣味值F_i（1≤F_i≤1000）。

奶牛也知道每条奶牛小道的信息。小道i将景点x连接到景点y, 并且需要T_i（1≤T_i≤1000）的时间才能通过。相对于路上的时间，参观景点的时间可以忽略不计。

为了获得最佳体验，奶牛们希望最大程度的提高她们单位时间所获得的趣味值。当然景点只在第一次访问时才有趣，奶牛们可能会不止一次穿过景点，但是多次访问并不会增加她们的快乐值。

请帮助奶牛们找到他们可以达到的单位时间最大趣味值。

第1行：两个空格分隔的整数N和M。

第2到L+1行：第i+1行包含一个正数F_i，表示第i个景点的趣味值。

第L+2到低L+P+1行：每行三个空格的整数x, y, t, 表示有一条奶牛小道从景点x通向景点y，所需时间为t。

他们可以达到的单位时间最大趣味值。