【UR #4】追击圣诞老人
在元旦激光炮的轰炸下，圣诞老人终于招架不住仓皇而逃，元旦三侠立刻展开追击行动。
有 $n$ 座城市，之间有 $n - 1$ 条道路连接成一个树形结构。每个城市有一个停留时间 $w_i$，只要圣诞老人来到 $i$ 号城市就必须停留 $w_i$ 的时间休息一下。
圣诞老人的逃跑路线可以用长度 $l$ 的序列 $s_1, s_2, \dots, s_l$ 表示（$l$ 是某个正整数），他会依次飞过 $s_1, s_2, \dots, s_l$ 号城市然后飞向火星找楼主聊人生，耗费的时间为经过的城市的停留时间之和，即 $\sum_{i = 1}^l w_{s_i}$。（圣诞老人可能经过同一个城市多次）
由于元旦三侠身手敏捷，圣诞老人在城市 $i$ 的时候下一步能飞到的城市是受限制的。对于每个城市 $i$ 有三个整数参数 $a_i, b_i, c_i$ （$1 \leq a_i, b_i, c_i \leq n$）。从城市 $i$ 出发能飞到城市 $j$ 当且仅当下面三个条件中有至少一个成立：
- 从城市 $a_i$ 出发沿道路行走到城市 $b_i$ 必经过城市 $j$。
- 从城市 $b_i$ 出发沿道路行走到城市 $c_i$ 必经过城市 $j$。
- 从城市 $c_i$ 出发沿道路行走到城市 $a_i$ 必经过城市 $j$。
所以圣诞老人的长度为 $l$ 的逃跑路线 $s$ 必须满足对于所有的 $1 \leq i < l$ 能从 $s_i$ 出发飞到 $s_{i + 1}$。
由于圣诞老人在和元旦三侠玩心理战，他会选择耗费时间前 $k$ 小的逃跑路线之一（长度 $l$ 不限）。请帮助元旦三侠找出耗费时间前 $k$ 小的逃跑路线的耗费时间吧。
由于世界被圣诞老人毁灭得差不多了，元旦三侠手上的电脑只有 $100\texttt{MB}$内存。请节约使用内存。测评机是 64 位机，指针类型和 long 类型均为 $8$ 个字节。
消灭圣诞老人！地球属于人类！
输入格式
第一行两个正整数 $n, k$。
第二行 $n$ 个整数，第 $i$ 个整数表示 $w_i$。保证 $1 \leq w_i \leq 10^8$。
第三行 $n - 1$ 个整数，第 $i$ 个整数即 $p_{i + 1}$ 表示 $i + 1$ 号城市与 $p_{i+1}$ 号城市之间有道路连接。保证 $1 \leq p_{i + 1} < i + 1$。
接下来 $n$ 行，第 $i$ 行包含三个整数 $a_i, b_i, c_i$。保证 $1 \leq a_i, b_i, c_i \leq n$。
输出格式
$k$ 行，每行一个整数，第 $i$ 行表示第 $i$ 小的逃跑路线的耗费时间。
4 9
1 10 15 1000
1 2 2
2 2 4
2 2 3
1 3 4
3 3 4
1
10
11
15
16
20
21
25
25
样例二
见样例数据下载。这组样例满足 $a_i = b_i$。
样例三
见样例数据下载。
限制与约定
| 测试点编号 | $n$ | $k$ |
|---|---|---|
| 1, 2 | $n = 5$ | $k = 10$ |
| 3, 4 | $n = 100$ | $k = 100$ |
| 5, 6 | $n = 1000$ | $k = 50000$ |
| 7, 8 | $n = 1000$ | $k = 10^5$ |
| 9, 10 | $n = 15000$ | $k = 10^5$ |
| 11, 12 | $n = 20000$ | $k = 10^5$ |
| 13, 14 | $n = 10^5$ | $k = 10^5$ |
| 15, 16 | $n = 10^5$ | $k = 5 \times 10^5$ |
| 17, 18 | $n = 5 \times 10^5$ | $k = 10^5$ |
| 19, 20 | $n = 5 \times 10^5$ | $k = 5 \times 10^5$ |
对于所有编号为奇数的测试点，输入中所有 $a_i = b_i$。
保证答案小于等于 $10^8$。
时间限制：$3\texttt{s}$
空间限制：$100\texttt{MB}$