The tightly bound son of the mountains
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 a high level. Among the theoretical topics he taught was the concept of strong connectivity components. In real life, an unexpected component was Snark, who suggested hosting the "Grand Prix of Two Capitals," which further engaged Eldar.
Despite these connections, Eldar's strength remained undiminished; instead, he became more focused on solving the following problem:
You are given a directed graph with n vertices and m_1 edges. It is known that there are vertices s and t such that all vertices are reachable from s, and t is reachable from all vertices. Additionally, there is another set of edges on the same set of vertices, consisting of m_2 elements, each with an assigned integer weight.
Your task is to add some edges from the second set to the graph so that the following conditions are satisfied:
The graph with the added edges must be strongly connected, meaning each vertex must be reachable from every other vertex.
The total weight of the added edges must be minimized.
While Eldar is preoccupied with his connections to Ivan, Snark, and the upcoming Grand Prix of Two Capitals, he has tasked you with solving this problem. You need to determine whether a solution exists, and if it does, calculate the necessary details.
Input
The first line contains an integer n (1 ≤ n ≤ 100000). The second line contains a non-negative integer m_1. The following m_1 lines describe the edges of the given graph, with each edge specified by its start and end vertices. The next line contains a non-negative integer m_2. The subsequent m_2 lines describe the edges that can be added, with each edge specified by its start and end vertices and its weight, an integer ranging from -10^9 to 10^9, inclusive. It is known that 0 ≤ m_1 + m_2 ≤ 500000.
Output
On the first line, output "YES" or "NO" to indicate whether a solution exists. If a solution does exist, output three additional lines. The first line should contain the total weight of the added edges. The second line should specify the number of added edges. Finally, list the numbers of the added edges, each on a separate line. The edges are numbered starting from one, in the order they appear in the input file. Each added edge should be listed exactly once.