题号：NC21648
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
牛牛: ''牛妹快来看这个题是最小的最大''
牛牛: ''此题一定是二分无疑了''
牛妹: "二分能过此题我请你吃牛客食堂吧"
给你一个无向连通图，点的标号为0到n-1没有自环与重边，有点权与边权
定义一条路径的难度值为路径上最大的点权乘上最大边权
对于一对点(a,b),令d(a,b) 为a到b的路径中难度值最小的路径,求所有的d(a,b)之和(0 ≤ a < b ≤ n-1)
输入描述:
第一行输入两个整数n,m (2 ≤ n ≤ 300, n - 1 ≤ m ≤ min(2500, n*(n-1)/2))
第二行输入m个整数ai
第三行输入m个整数bi
第四行输入m 个整数wi(1≤ wi ≤ 106)
第五行输入n个整数vi(1≤ vi ≤ 106)
ai,bi之间有一条无向边，权值为wi
每个点的点权是vi
输出描述:
输出一个整数
示例2
输入
复制
3 3
0 0 1
1 2 2
10 11 12
6 5 4
示例3
输入
复制
3 3
0 0 1
1 2 2
100 1 1
1 1 100
示例4
输入
复制
11 10
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
1000000 1 1000000 1 1000000 1 1000000 1 1000000 1
1000000 1 1000000 1 1000000 1 1000000 1 1000000 1 1000000
备注:
子任务1： n <= 50
子任务2：n <= 100
子任务3：n <= 300