Planar Max Cut

Some of you may know how to find a minimum cut in a graph. Some of you may also know that the maximum cut problem is NP-complete (more precisely, the decision version of finding a cut of value at least $k$ is NP-complete). For some restricted classes of graphs, however, the problem is easier than in the general case.

Consider the Planar Maximum Cut problem. You are given an undirected graph $G$ with $n$ vertices and $m$ edges, where $V = \{v_1, \dots, v_n\}$. The graph is planar, and its embedding is given: the coordinates of every vertex are known, and when the edges are drawn as segments, no two edges share an internal point. Edge $j$ has an integer cost $c_j$.

Partition the vertices into two disjoint sets $A$ and $B$ ($A \cup B = V$) so that the total cost of the cut edges is maximized. An edge is a cut edge if one of its endpoints is in $A$ and the other is in $B$.

The first line contains two integers $n$ and $m$ ($1 \le n \le 200$, $1 \le m \le 1000$).

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^4 \le x_i, y_i \le 10^4$), the coordinates of vertex $i$. No two points coincide.

Each of the next $m$ lines contains three integers $a_j$, $b_j$, and $c_j$ ($1 \le a_j, b_j \le n$, $a_j \ne b_j$, $0 \le c_j \le 10^5$). This means edge $j$ connects vertices $a_j$ and $b_j$ and has cost $c_j$.

Print the maximum total cost of the cut edges on the first line.

On the second line, print $n$ integers $s_1, s_2, \dots, s_n$. Print $s_i = 0$ if vertex $i$ is in $A$, and $s_i = 1$ if vertex $i$ is in $B$. If several answers exist, print any of them.