23868번 - Rooted MST 서브태스크다국어

문제

You are given a simple undirected weighted graph with $n+1$ vertices numbered 0,ドル 1, \ldots, n$ and $n + m$ edges.

The weight of an edge between vertices 0ドル$ and $i$ is $a_i$ for 1ドル \leq i \leq n$.

The weight of an edge between vertices $u_i$ and $v_i$ is $w_i$ for 1ドル \leq i \leq m$.

You need to answer $q$ queries, in each query, you are given two integers $i, w$ and you need to change the weight of an edge from 0ドル$ to $i$ to $w$ and find the weight of the minimum spanning tree in the graph.

Note that changes to the weights are permanent, i.e. they stay after each query.

입력

The first line of input contains two numbers $n, m$ (2ドル \leq n \leq 300,000,円 0 \leq m \leq 300,000円$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ (1ドル \leq a_i \leq 10^9$).

Each of the next $m$ lines contains three integers $u_i, v_i, w_i$ (1ドル \leq u_i, v_i \leq n, 0 \leq w_i \leq 10^9$).

It is guaranteed that the given graph is simple, in other words, it contains no loops and multiple edges.

The next line contains one integer $q$ (1ドル \leq q \leq 300,000円$).

Each of the next $q$ lines contains two integers $i, w$ (1ドル \leq i \leq n, 1 \leq w \leq 10^9$).

출력

For each query print one integer: the weight of the minimum spanning tree in the graph after the first $i$ queries.

제한

서브태스크

힌트