Rooted MST

정점이 $0, 1, \ldots, n$으로 번호 매겨진 $n+1$개의 정점과 $n + m$개의 간선을 가진 단순 무방향 가중 그래프가 주어진다.

정점 $0$과 $i$ 사이 간선의 가중치는 $1 \leq i \leq n$에 대해 $a_i$이다.

정점 $u_i$와 $v_i$ 사이 간선의 가중치는 $1 \leq i \leq m$에 대해 $w_i$이다.

$q$개의 쿼리에 답해야 한다. 각 쿼리에서는 정수 $i, w$가 주어지며, 정점 $0$과 $i$ 사이 간선의 가중치를 $w$로 바꾼 뒤 그래프의 최소 스패닝 트리 가중치를 구한다. 가중치 변경은 영구적이어서 이후 쿼리에도 그대로 남는다.

첫 줄에 정수 $n, m$이 주어진다 ($2 \leq n \leq 300000$, $0 \leq m \leq 300000$).

둘째 줄에 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \leq a_i \leq 10^9$).

이후 $m$개의 줄에 정수 $u_i, v_i, w_i$가 한 줄씩 주어진다 ($1 \leq u_i, v_i \leq n$, $0 \leq w_i \leq 10^9$).

주어지는 그래프는 단순 그래프이며, 자기 루프와 다중 간선이 없음이 보장된다.

다음 줄에 정수 $q$가 주어진다 ($1 \leq q \leq 300000$).

이후 $q$개의 줄에 정수 $i, w$가 한 줄씩 주어진다 ($1 \leq i \leq n$, $1 \leq w \leq 10^9$).

각 쿼리마다, 그 쿼리를 적용한 뒤의 최소 스패닝 트리 가중치를 한 줄에 하나씩 출력한다.