시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB259940.909%

문제

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.

서브태스크

번호배점제한
110

$n, m, q \leq 2000$

210

All weights are either $1$ or $2$

310

$w = 1$ in all queries

410

$i = 1$ in all queries

510

$i \le 5$ in all queries

610

$m = n - 1, u_i = v_i - 1$

720

$n, m, q \leq 150\,000$

820

No additional constraints

예제 입력 1

5 7
3 2 1 2 1
1 5 1
1 3 2
2 5 2
4 5 2
3 4 1
2 4 2
1 2 1
10
3 2
2 3
4 1
3 2
5 1
5 3
3 1
2 3
4 3
5 1

예제 출력 1

6
6
5
5
5
6
6
6
6
5

채점 및 기타 정보

  • 예제는 채점하지 않는다.