The tightly bound son of the mountains#1975
Eldar Bogdanov, a proud son of the mountains, is a strong man. However, he has commitments to Ivan Metelsky to ensure that his day at the Winter School 2011 is spent at the highest level. Among the theoretical material he taught was the topic of strong connectivity components. In real life, an unexpected component was Snark, who suggested hosting the "Grand Prix of Two Capitals", which further involved Eldar.
Despite these connections, Eldar became even more immersed in solving the following problem:
You are given a directed graph with vertices and m_1 edges. It is known that there exist vertices and such that all vertices are reachable from , and is reachable from all vertices. Additionally, another set of m_2 edges is given on the same set of vertices. Each edge in this second set has an assigned integer weight.
You must add some edges from the second set to the graph so that the following conditions are satisfied:
With the added edges, the graph must be strongly connected (each vertex must be reachable from every other vertex).
The total weight of the added edges must be minimized.
While Eldar is deeply engaged with his commitments, he asks you to solve this problem and inform him of the existence of a solution. If a solution exists, calculate the required values.
The first line contains an integer (1 \leq n \leq 100\,000). The second line contains a non-negative integer m_1. The following m_1 lines describe the edges of the original graph. Each edge is given by its start and end vertices.
The next line contains a non-negative integer m_2. The following m_2 lines describe the edges that can be added. Each edge is given by its start and end vertices and its weight — an integer from -10^9 to 10^9, inclusive. It is known that 0 \leq m_1 + m_2 \leq 500\,000.
On the first line, output "YES" or "NO" depending on whether a solution exists. If a solution exists, output three more lines: the first should be the total weight of the added edges, the second should be the number of added edges, and then the numbers of the added edges used, each on its own line. The edges are numbered starting from one, in the order in which they appear in the input file. Each added edge should be listed exactly once.
Example 1