给定一个由n个点和n-1条边组成的无向连通图（即一棵树），每一条边都有一个权值代表走过它所需要的时间花费，每个点上面有初始有一个苹果，每个苹果有一个成熟度。
由于苹果不熟或者熟的太透了都不会好吃，所以现在米咔想摘一个成熟度在范围[x,y]的苹果来做苹果派。现在需要你来执行m条操作。
1 u x：在某一个点u新出现了一个成熟度为x的苹果。（1≤u≤n,1≤x≤10000）
2 u x y：询问米咔从某一个点u出发，去摘一个成熟度在[x，y]范围内的苹果并回到u的最小时间花费。（1≤u≤n,1≤x≤y≤10000）
第一行两个正整数n，m（1 ≤ n，m ≤100000）
第二行n个正整数，代表每个点苹果的成熟度。接下来n-1行每行三个正整数u,v,w，表示u,w间的边权是w。保证给出的图是一棵树。接下来m行每行一个操作，格式见题目描述。
保证苹果的成熟度和边权都不大于10000。
对于每个询问，输出对应答案。如果无法完成，输出-1。