Berland Bruteforce Corporation 的总部由 $n$ 个房间组成，这些房间通过 $n-1$ 条通道连接。在任意两个房间之间有且仅有一条路径（熟悉图论的人会立即认出这是一个无向树）。假设房间编号为从 $1$ 到 $n$ 的连续整数。在房间 $i$ 中有 $e_i$ 名员工。每条通道的长度（以米为单位）已知。
最近的地震促使 BBC 董事会决定为员工制定疏散计划。计划中应包含一个疏散点，该点可以位于某个房间内，也可以位于通道上的任意位置。如果是后者，则会创建一个新房间。这个新房间将长度为 $L$ 的通道分为长度分别为 $L_1$ 和 $L_2$ 的两条通道（$L_1 + L_2 = L$）。
一旦确定了疏散点，疏散过程如下：在时间 $0$（疏散开始时），所有员工同时尝试开始向疏散点移动。一个人走 $1$ 米需要正好 $s$ 秒。通道的容量有限，且所有通道的容量 $c$ 相同：在每个时间步，最多有 $c$ 个人可以进入通道。让我们稍微澄清一下：考虑某条通道。显然，人们只会沿两个可能方向中的一个通过它。在时间 $0$，最多有 $c$ 个人可以进入通道。然后，直到时间 $1$ 之前，没有人可以进入该通道；在时间 $1$ 时，再次最多有 $c$ 个人可以进入，依此类推。在任何时刻，房间或通道内的人数没有限制。
BBC 董事会对能够最小化疏散时间的计划感兴趣：即所有人到达疏散点的时间。请帮助他们制定该计划。
输入格式
第一行包含三个整数 $n, c$ 和 $s$ ($1 \le n \le 10^5, 1 \le c \le 10^4, 1 \le s \le 100$)：房间数量、每条通道的容量以及走 $1$ 米所需的时间。第二行包含 $n$ 个整数 $e_1, e_2, \dots, e_n$ ($1 \le e_i \le 10^6$)。接下来的 $n-1$ 行，每行包含三个整数 $u, v$ 和 $d$ ($1 \le u, v \le n, 1 \le d \le 10^4$)，表示房间 $u$ 和 $v$ 之间存在一条长度为 $d$ 米的通道。
输出格式
打印疏散点的最佳位置。如果你打算将疏散点放置在现有房间中，请打印其编号。否则，打印三个数字 $u, v$ 和 $x$，表示疏散点必须放置在连接房间 $u$ 和 $v$ 的通道上，且距离 $u$ 为 $x$ 米。数字 $x$ 必须属于区间 $(0, l)$，其中 $l$ 是房间 $u$ 和 $v$ 之间通道的长度。
如果你的计划中的疏散时间与最优时间的绝对误差或相对误差不超过 $10^{-9}$，则你的答案将被视为正确。
样例
输入 1
2 2 1 5 5 1 2 3
输出 1
1 2 1.500000000000
输入 2
2 2 1 5 10 1 2 3
输出 2
1 2 2.500000000000
输入 3
3 2 10 8 6 8 1 2 10 2 3 10
输出 3
2
输入 4
4 3 1 3 8 4 7 1 2 2 2 3 1 2 4 5
输出 4
2 4 1.500000000000
说明
让我们逐步分析第四个样例的疏散过程：
- $t = 0$:
- $3$ 人从房间 $1$ 进入通道 $(1, 2)$，他们将在 $t = 2$ 时到达房间 $2$。
- $3$ 人从房间 $3$ 进入通道 $(3, 2)$，他们将在 $t = 1$ 时到达房间 $2$。
- $3$ 人从房间 $4$ 进入通道 $(4, 2)$，他们将在 $t = 3.5$ 时到达疏散点。
- $3$ 人从房间 $2$ 进入通道 $(2, 4)$，他们将在 $t = 1.5$ 时到达疏散点。
- $t = 1$:
- $1$ 人从房间 $3$ 进入通道 $(3, 2)$，她将在 $t = 2$ 时到达房间 $2$。
- $3$ 人从房间 $4$ 到达房间 $2$。
- $3$ 人从房间 $4$ 进入通道 $(4, 2)$，他们将在 $t = 4.5$ 时到达疏散点。
- $3$ 人从房间 $2$ 进入通道 $(2, 4)$，他们将在 $t = 2.5$ 时到达疏散点。
- $t = 2$:
- $3$ 人从房间 $1$ 和 $1$ 人从房间 $3$ 到达房间 $2$。
- $1$ 人从房间 $4$ 进入通道 $(4, 2)$，她将在 $t = 5.5$ 时到达疏散点。
- $3$ 人从房间 $2$ 进入通道 $(2, 4)$，他们将在 $t = 3.5$ 时到达疏散点。
- $t = 3$:
- $3$ 人从房间 $2$ 进入通道 $(2, 4)$，他们将在 $t = 4.5$ 时到达疏散点。
- $t = 4$:
- $3$ 人从房间 $2$ 进入通道 $(2, 4)$，他们将在 $t = 5.5$ 时到达疏散点。
疏散在 $5.5$ 秒时结束。