有n个面包,每个面包有大小a[i],有m条无向边,每条边连接x[i],y[i],边权为w[i],现在有一只“巨不溜”,他要从起点s开始走,经过若干边到达t,因为他叫“巨不溜”,所以他一定要吃到路径中最大的那一个面包,又因为他非常巨,所以他会找到路径中最大的那一条边,这样他要付出最大的面包大小*最大的边权大小的代价.而他想最小化这个代价.

问对于1~n中每一个s和t,他们之间的最短路是多少.

第一行两个整数n,m,分别表示无向图的点数和边数。

第二行n 个正整数,第i个正整数表示点i 的点权。

接下来m 行每行三个正整数ui,vi,wi,分别描述一条边的两个端点和边权。

n行每行n个整数,第i行第j个整数表示从i到j的路径的最小权值,如果从i不能到达j,则该值为-1.

特别地,当i=j时输出0.

对于20%的数据，n<=5,m<=8。

对于50%的数据，n<=50

对于100%的数据，n<=500,m<=n*(n-1)/2，边权和点权不超过10^9.

SDSC2018