## Description

Problem: Cycle Breaking

Cycle breaking serves as a fundamental technique for many applications, e.g., resolving resource deadlock or

simplifying a problem instance. In graph theory, a cycle is a path where the first and the last vertices are

the same. A graph without cycles is called an acyclic graph. Given a graph G = (V, E) which may contain

cycles, we want to remove some edges to make the graph acyclic with minimum total cost (weight). Such a

problem is so-called the cycle breaking or cycle removal problem. For example, Figure 1 (a) is a weighted

undirected graph Gu with cycles. We can remove e01 and e34 to make it acyclic with total cost = 3 + 5 = 8.

For the weighted directed graph Gd in Figure 1 (b), there is only one cycle C143. So we only need to remove

e43 with total cost = 5. Cycle breaking for an (unweighted or weighted) undirected graph can be solved in

polynomial time. The problem for a weighted directed graph, however, is also known as a minimum feedback

arc set problem, which is a NP-hard problem. In this assignment, test cases contain three types of graph

instances: 1) unweighted undirected graph, 2) weighted undirected graph, and 3) weighted directed graph.

(a) weighted undirected graph (b) weighted directed graph

Figure 1: Graph with cycles.

Input

The input will be a graph with only one connected component which may contain cycles or not. The first line

of the input is a character “u” or a character “d”, which indicates the input graph is an undirected graph or

a directed graph, respectively. The second line is an integer n, denoting the total number of vertices. The

indices of these nodes will be continuous from 0 to n − 1. The third line is an integer m, denoting the total

number of edges. In the following m lines, each contains three integers i, j and w, denoting an edge from

vertex i to vertex j with weight w, −100 ≤ w ≤ 100. For test cases of unweighted undirected graph, the

weight of all edges will equal to 1. Please note that the order of vertex i and j implies the direction of the

edge in a directed graph, while it does not matter in an undirected graph. A single “0” (zero) in the input

line signifies the end of input. For undirected graph instances, 1 ≤ n ≤ 10000 and 1 ≤ m ≤ 50000000. For

directed graph instances, 1 ≤ n ≤ 5000 and 1 ≤ m ≤ 10000.

Output

The output file should report the total weight of removed edges to make the input graph acyclic, followed

by a list of these removed edges and their weights. The graph must remain connected (one connected

component) after the edges are removed. The output edges can be in arbitrary order. If the input graph

has no cycles, you should output a line with single “0” (zero) in your output file.

Here are some input/output examples:

Sample Input 1 Sample Output 1 Sample Input 2 Sample Output 2

u 8 d 5

8 0 1 3 8 4 3 5

9 3 4 5 9

0 1 3 0 1 3

0 2 5 0 2 5

1 3 10 1 4 8

1 4 8 2 5 9

2 5 9 3 1 10

3 4 5 3 5 11

3 5 11 4 3 5

3 6 12 4 7 6

4 7 6 6 3 12

0 0

Command-line Parameter:

The executable binary must be named as ‘cb” and use the following command format.

./cb