T145192 【2020.8.23NOIP模拟赛】最优路线

一个 $n$ 个点 $m$ 条边的无重边无自环的无向图，点有点权，边有边权，定义一条路径的权值为路径经过的点权的最大值乘边权最大值。求任意两点间的权值最小的路径的权值。

第一行两个整数 $n,m$，分别表示无向图的点数和边数。 第二行 $n$ 个正整数，第 $i$ 个正整数表示点 $i$ 的点权。 接下来 $m$ 行每行三个正整数 $u_i,v_i,w_i$，分别描述一条边的两个端点和边权。

$n$ 行每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数表示从 $i$ 到 $j$ 的路径的最小权值，如果从 $i$ 不能到达 $j$，则该值为 $-1$。特别地，当 $i=j$ 时输出 $0$。

对于 $20\%$ 的数据，$n\le 5,m\le 8$。 对于 $50\%$ 的数据，$n\le 50$。 对于 $100\%$ 的数据，$n\le 500,m\le n(n-1)/2$，边权和点权不超过 $10^9$。