NC21648. 牛牛与牛妹的赌约

描述

输入描述

第一行输入两个整数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

输出描述

输出一个整数

示例1

输入:

2 1
0
1
5
3 6

输出:

30

示例2

输入:

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

输出:

186

示例3

输入:

3 3
0 0 1
1 2 2
100 1 1
1 1 100

输出:

300

示例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

输出:

50000005000000

原站题解