"He is from Jakarta, not Bali."
Translation:Dia dari Jakarta, bukan dari Bali.
Tidak -> Negate adjective and verb
Bukan -> Negate noun and adverb
In this case, "bukan" negates the word "Bali" as a noun. It's a bit hard to explain, but as an Indonesian, I would think of it like this :
Saya bukan dari Bali -> I'm not from Bali (but from somewhere else).
Saya tidak dari Bali -> I'm not from Bali (I wasn't coming from Bali)
So "Tidak" negates the verb "Dari", while "Bukan" negates the noun "Bali". I hope it makes sense