{"problem":{"name":"Graph","description":{"content":"Takahashi found an undirected connected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$. The $i$\\-th edge connects vertices $a_i$ and $b_i$, and has a weight of $c_i$.","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"asaporo_c"},"statements":[{"statement_type":"Markdown","content":"Takahashi found an undirected connected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$. The $i$\\-th edge connects vertices $a_i$ and $b_i$, and has a weight of $c_i$.\nHe will play $Q$ rounds of a game using this graph. In the $i$\\-th round, two vertices $S_i$ and $T_i$ are specified, and he will choose a subset of the edges such that any vertex can be reached from at least one of the vertices $S_i$ or $T_i$ by traversing chosen edges.\nFor each round, find the minimum possible total weight of the edges chosen by Takahashi.\n\n## Constraints\n\n*   $1 ≦ N ≦ 4,000$\n*   $1 ≦ M ≦ 400,000$\n*   $1 ≦ Q ≦ 100,000$\n*   $1 ≦ a_i,b_i,S_i,T_i ≦ N$\n*   $1 ≦ c_i ≦ 10^{9}$\n*   $a_i \\neq b_i$\n*   $S_i \\neq T_i$\n*   The given graph is connected.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$ $c_1$\n$a_2$ $b_2$ $c_2$\n:\n$a_M$ $b_M$ $c_M$\n$Q$\n$S_1$ $T_1$\n$S_2$ $T_2$\n:\n$S_Q$ $T_Q$\n\n## Partial Scores\n\n*   In the test set worth $200$ points, $Q = 1$.\n*   In the test set worth another $300$ points, $Q ≦ 3000$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"asaporo_c","tags":[],"sample_group":[["4 3\n1 2 3\n2 3 4\n3 4 5\n2\n2 3\n1 4","8\n7\n\nWe will examine each round:\n\n*   In the $1$\\-st round, choosing edges $1$ and $3$ achieves the minimum total weight of $8$.\n*   In the $2$\\-nd round, choosing edges $1$ and $2$ achieves the minimum total weight of $7$."],["4 6\n1 3 5\n4 1 10\n2 4 6\n3 2 2\n3 4 5\n2 1 3\n1\n2 3","8\n\nThis input satisfies the additional constraints for both partial scores."]],"created_at":"2026-03-03 11:01:13"}}