Weighted Min-Cut in bounded-genus graphs
For graphs embedded on a surface of genus g with bounded weights $w:E \rightarrow \mathbb{Z}$, you can solve MAX-CUT in time $4^g poly(n)$ using an algorithm of Gallucio, Loebl and Vondrák. Applying it to your instance after taking the opposite weights and looking whether the result is positive seems to solve your problem.