통행료

해피랜드는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 도시로 이루어진 나라이다. $1$번 도시가 수도이다. 처음에 도시들은 $1$번부터 $M$번까지 번호가 매겨진 $M$개의 양방향 도로로 연결되어 있으며, 이 도로들만 이용해도 모든 도시에서 $1$번 도시로 갈 수 있음이 보장된다. 모든 도로는 유료 도로여서, $i$번 도로를 이용하려면 그 도로의 소유주에게 통행료 $c_i$센트를 내야 한다. 모든 $c_i$는 서로 다르다.

최근에 억만장자 그리디 씨가 $K$개의 새 도로를 완공했고, 이 도로들은 모두 그가 소유한다. 그는 각 새 도로의 통행료를 원하는 양의 정수로 정할 수 있으며(새 도로들의 통행료는 서로 같아도 되고 달라도 된다), 이 통행료들을 내일 발표해야 한다.

$2$주 뒤에 거대한 축제가 열린다. 각 도시 $j$마다 정확히 $p_j$명이 도시 $j$에서 출발하여 수도인 $1$번 도시로 이동한다. 이들은 축제 전날 발표되는, 선택된 도로 집합만을 이용할 수 있다. 전통에 따라 이 도로 집합은 해피랜드에서 가장 부유한 사람인 그리디 씨가 고른다. 같은 전통에 의해, 선택된 집합은 (a) 모든 도시에서 여전히 $1$번 도시로 갈 수 있게 해야 하고, (b) 그러한 모든 집합 중 통행료의 총합이 최소여야 한다. 즉, 선택된 도로들은 통행료를 간선 가중치로 하는 최소 신장 트리를 이루어야 한다. 총합이 최소인 집합이 여러 개일 때에는 그리디 씨가 그중 어느 것이든 고를 수 있다.

그리디 씨는 새 도로에서만 수익을 얻는다(기존 도로는 하나도 소유하지 않는다). 한 도로의 수익은 그 통행료에 그 도로를 지나간 사람 수를 곱한 값이다. 즉, $i$번 도로의 통행료가 $c_i$이고 $p$명이 그 도로를 지나갔다면 수익은 $c_i \cdot p$이다.

그리디 씨는 새 도로들의 통행료를 잘 정하고, 통행료 총합이 최소인 집합이 유일하지 않을 때에는 선택할 도로 집합도 잘 골라서, 통행료 총합이 최소여야 한다는 전통은 지키면서 $K$개의 새 도로에서 얻는 총수익을 최대로 만들고 싶다. 그가 얻을 수 있는 최대 총수익을 구하여라.

첫째 줄에 정수 $N$, $M$, $K$가 주어진다.

다음 $M$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $c_i$가 주어진다. 이는 $i$번 기존 도로가 도시 $a_i$와 $b_i$를 연결하며 통행료가 $c_i$임을 뜻한다.

다음 $K$개의 줄에는 각각 두 정수 $x_i$, $y_i$가 주어진다. 이는 $i$번 새 도로가 도시 $x_i$와 $y_i$를 연결함을 뜻한다.

마지막 줄에는 $N$개의 정수 $p_1, p_2, \dots, p_N$이 주어지며, $p_j$는 도시 $j$에서 출발하는 사람 수이다.

제약:

• $1 \le N \le 100000$
• $1 \le K \le 20$
• $1 \le M \le 300000$
• $1 \le c_i, p_j \le 10^6$
• 모든 $c_i$는 서로 다르다.
• 어떤 두 도시 사이에도 도로는 최대 한 개이다(기존 도로와 새 도로를 모두 포함하여).
• 기존 도로만 이용해도 모든 도시에서 $1$번 도시로 갈 수 있다.

그리디 씨가 얻을 수 있는 최대 총수익을 정수 하나로 출력한다.

위 그림의 상황을 생각해 보자. 그리디 씨는 새 도로 $(1,3)$의 통행료를 $5$로 정하는 것이 좋다. 이렇게 하면 도로 $(3,5)$, $(1,2)$, $(2,4)$, $(1,3)$을 선택할 수 있고, 이때 통행료 총합은 가능한 최솟값인 $14$이다. 그러면 도시 $3$의 $30$명과 도시 $5$의 $50$명이 $1$번 도시로 가는 길에 이 새 도로를 지나가므로, 수익은 $(30 + 50) \times 5 = 400$이 된다.

만약 $(1,3)$의 통행료를 $10$으로 정했다면, 전통에 따라 그리디 씨는 통행료 총합이 최소가 되는 유일한 집합인 $(3,5)$, $(1,2)$, $(2,4)$, $(2,3)$을 선택해야 하고, 아무도 새 도로를 이용하지 않아 수익이 $0$이 된다.