I'd say learn Hokkien first, which as a Min dialect has a more conservative phonology, which will help more than Mandarin when learning Japanese and Korean. The rest is a matter of test.
Also, I recommend using a website like the one I made (in alpha), which helps comparing the pronunciation of vocabulary of Sinitic origin: http://144.24.197.67/entry/e5b585e5-aba3-0000-0000-000000000...