直播

每一场人气直播的背后，都需要强大的云资源保障。华为云通过搭建庞大的云网络、使用先进的流量调度技术，为用户提供优质的直播服务。

现在有一个地区的用户正在收看一位明星的直播。

直播网络可以看作是一幅 $n$ 个节点、$m$ 条边的有向无环连通图，$1$ 号节点是该地区的骨干节点，即直播数据到达该地区的第一个节点，其余节点用 $v_i=0$ 表示普通路由节点，$v_i=1$ 表示 CDN 节点，$v_i=2$ 表示观看直播的用户节点。普通路由节点只能做转发工作（任何进入该点的数据都被唯一地转发出去）；CDN 节点可以将收到的直播数据缓存并无限转发；用户节点需要接收自己的数据，同时也可以当作普通路由节点转发其他数据。每条边有一个权值 $c_i$，表示该边的带宽，若有 $x$ 项传输工作使用该边，则每项传输工作在该边的传输速率为 $\lfloor \frac{c_i}{x} \rfloor$。

你需要为每个用户安排一条数据通道（即从 $1$ 号节点到该用户节点的路径）。每个用户观看直播的实际带宽为其数据传输工作在路径上的最小传输速率。由于实际带宽会影响延时，进而对直播效果产生较大影响，你需要使得所有用户的最小实际带宽越大越好。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n,m$，表示有向图的点数和边数。（$1 \le n \le 50,\ \ n-1 \le m \le 200$）

第二行 $n-1$ 个整数 $v_2,\cdots,v_n$，表示 $2,\cdots,n$ 每个节点的类型。（$v_i \in \{0,1,2\}$）

接下来 $m$ 行，每行三个整数 $u,v,c$，表示有一条从 $u$ 到 $v$、总带宽为 $c$ 的边。（$1 \le c \le 10^6$）

保证图连通，且 $1$ 号节点能到达所有用户节点，**最多只有 5 个 CDN 节点**。

$T \le 20$ 且最多只有 3 组数据满足 $n \ge 10$。

一行，一个整数，表示所有用户最小实际带宽的最大值。

1
7 7
1 0 2 2 2 2
1 2 5
1 3 10
2 4 7
2 5 5
3 5 3
3 6 12
6 7 7

5

$4$ 号点选择 $1 \to 2 \to 4$，$5$ 号点选择 $1 \to 2 \to 5$，$6$ 号点选择 $1 \to 3 \to 6$，$7$ 号点选择 $1 \to 3 \to 6 \to 7$。

由于 $2$ 号点是 CDN 节点，因此它只需接受一份数据，可以传出两份数据。

边 $(1,3)$ 和 $(3,6)$ 都是两项传输工作共同使用，因此实际带宽分别为 $5$ 和 $6$。

2022 CCPC 华为云计算挑战赛