Graph without oriented cycles

The second practical homework. The deadline is 8.5.2016.

Problem description

Given an oriented graph with weighted edges, the optimization problem is to remove a set of edge with the minimal weight such that the remaining graph has no oriented cycle. Your task is to write a program which solves the problem.

You can assume that the graph is without loops and multiple edges, oriented cycles of length 2, and weights on edges are positive. Think over that there always exists an optimal solution although it may not be unique.

Data format

Your program must read an instance of the problem from the standard input and result must be printed on the standard output. On the input, the first line of contains the number of vertices v (indexed by 0, ..., v-1) and number of edges e of the graph. Then, e lines follows and every one contains three integers identifying a head, a tail and weight of an edge. The output has to contain a list of removed edges (two number defining a head and a tail of an edge on every line).

Example input


4 6
0 1 4
0 2 3
0 3 1
1 2 4
2 3 2
3 1 5

Example output


2 3

Submitting your solution

Send an e-mail to your teaching assistant with
  • source code used to get your results (in case it consists of multiple files, please use ZIP or TAR to pack them),
  • how to compile your program (use Makefile in case it consists of multiple files), and
  • description of your algorithm in the PDF format.

Evaluation

Your program must produce a correct answer for arbitrary input, assuming sufficient amount of memory and time is provided. The main criteria determining the number of points received from this homework is the running time on inputs similar to the test ones. A trivial algorithm finds optimal solutions in one hour but it should not be hard to improve the algorithm to obtain expected results in one minutes.

The quality of source codes and documentation is also considered.

Test data

A pack of testing inputs contains few small input files (for debugging purposes only) and many input files used to measure the running time.

Rules

  • All the code which you submit must be original created by you without any external "inspiration".
  • Do not share your solution with anyone else so that your code does not become someone else's "inspiration". The only exception to this rule is submitting the assignment.
  • Your solution should be written in either C/C++ (recommended), Java, C#, BASH (awk) or Python. Your teaching assistant may allow using other programming languages.
  • In order to solve (integer) linear programming problems, the library GLPK or program GLPSOL can be used. Linear programming problem can also be formulated in the modelling language MathProg and then solved by GLPSOL. Your teaching assistant may allow using other solvers.
  • Your program must be easily compilable and it must run on GNU/Linux without any non-trivial dependencies (decided by your teaching assistant). For instance in C++, it should be sufficient the standard library and glpk.
  • Programs producing output in an incorrect format are rejected.

Hints

  • Read this page carefully.
  • Try to run your program in the Unix laboratory at Mala Strana to avoid unnecessary bugs.