Rules:

- each line starting with a “c” is considered a comment and thus skipped
- the first (non-comment) line contains the key “
**MAX-CUT**” followed by one or more <space> and by two integersand**n**[meaning:**m**is the number of nodes of the graph,*n*is the number of edges]**m** - every following (non-comment) line represents an edge and is described by two integers and a real number
separated by one or more <space>**i j w,** and**i**are distinct and in the range [1..*j***n**].is the weight of the edge**w**- the number of lines describing the edges of the graph must be equal to
**m** - loops (i.e., edges with
=**i**) are simply disregarded**j** - if multiple edges are present, i.e., if the same pair
appears more than ones (irrespective of the order of the two nodes), only one edge is considered with weight equal to the sum of the weights of all such pairs**i j**

**Example:**

Input file:

c

c An instance of MAX-CUT

c

MAX-CUT 4 5

1 2 1

1 3 1.0

1 4 1.0e1

2 3 2

3 4 -1