this is sounds very similar like one of the facebook hacker cup task this year..

So my first try would be, find the smallest minimum cut, let denote this number C..

After that make some greedy algo: find the smallest node id which can be a part of some cut which volumen is C.

So go through node and erase node v, after that run find minimum cut algo, if this cut volumen is C-1 we found the first node of the lexicographically smallest minimum cut..

after that find the second node, and so on.. minimum cut algo is O(N^3) , it seems to enough go through the node just once (this is N step), and we erase every edge maximum twice so this algo is about O(N^4*M)

Yes, that seems to work thanks, but isn't it's complexity O(N^3*(N+2*M))?