在公司的工作安排中，不同的工作可能是互相独立的，也可能是有依赖的。一个任务A是另外一个任务B的前置任务，要A完成后才能进行B，特别地，每个任务可能最多有2个前置任务，而前置任务本身可能也有前置任务。 这样的前置依赖结构可以用树表示，子节点是父节点的前置任务 当有一系列任务分配下来后，由于项目规划的需要，问当最后一个任务（根节点）完成，最少需要多少时间

输入描述:

第一行两个正整数m, n，分别代表总共有树上有m个节点，和树上有n条边，用空格分割下面有m个行，表示每个节点任务的id和所需要的时间，用空格分割下面有n行，每行为3个部分，表示树上的边，用空格分割，第一个数字为某非叶子节点（父节点）的id, 第二个为该边为left还是right，第三个为子节点的id注意：id彼此不会重复，id 1为根节点，2

输出描述:

一个整数，表示最后一个任务（根节点）完成，最少需要多少时间