dia是学生会长。她经常有信息要传达给别人。
学生会的阶层等级森严。每个阶级传达信息只能传达到自己的下属。
一个人可以有多个下属，但一个人最多只能有一个上级。
dia作为学生会长，很明显是没有上级的（即全学生会权利最大者）。
已知每个人传达到下属所消耗的时间。（传达给不同的下属，时间不一定相同）
现在dia有一个信息要传达给一个指定者。只有信息接收的指定者才需要理解信息（花费ai的时间）。她不想让效率太慢，于是她想找出最大时间消耗的那个路线（包括信息接收指定者所需要理解信息的时间），这样就能方便整改。
输入描述:
第一行一个正整数n，代表学生会的人数（dia是1号，其他人标记为2号到n号）。 （1≤n≤200000）
第二行有n-1个正整数ai，代表从2号到n号，每个人需要理解信息的时间。 （1≤a1≤100）
接下来的n-1行，每行有3个正整数x,y,k,代表x是y的上级，x向y传播信息需要消耗k的时间。（1≤x,y≤n,1≤k≤100）
输出描述:
一个正整数，代表dia选定某人作为信息接收指定者后，花费总时间的最大值。
示例1
说明
若dia指定3号为信息接受者，消耗时间为2+4=6。
若dia指定2号为信息接受者，消耗为4+3=7。
故最大值为7。
备注:
注：只有指定者需要理解信息，传达者不需要花费时间理解信息。