Minimal Cost to Connect Servers

You are given a network with n servers and m bidirectional links connecting some pairs of servers. Each link is described by three integers u, v, and w representing an edge between servers u and v with cost w.

In addition, you are given q queries. For each query, you are provided with a server k and an integer x. For that query, you add extra links from server k to all other servers with cost x and then determine the minimum cost required to connect all servers (i.e. the cost of the Minimum Spanning Tree (MST)). If it is impossible to connect all servers, output -1.

The servers are numbered from 1 to n. The added extra links for each query should be considered along with the original m links when computing the MST. All formulas and technical details are provided in LaTeX format whenever needed. For example, the cost of the MST can be represented as:

\(\min \{ \sum_{e \in MST} w_e \}\)

inputFormat

The input is given from standard input (stdin) and has the following format:

The first line contains two integers n and m, where n is the number of servers and m is the number of initial links.

The next m lines each contain three integers u, v, w, describing a bidirectional link between servers u and v with cost w.

The following line contains an integer q, indicating the number of queries.

Each of the next q lines contains two integers k and x, representing a query. For each query, a link from server k to every other server with cost x is added before computing the MST.

outputFormat

For each query, output a single line to standard output (stdout) containing the minimum cost to connect all servers after adding the extra links. If the network cannot be connected, output -1.## sample

4 3
1 2 1
2 3 2
3 4 4
2
1 3
4 1

6
3