Elemental gallium possesses several intriguing properties such as a low melting point, a density anomaly and an electronic structure in which covalent and metallic features coexist. In order to simulate this complex system, we construct an ab-initio quality interaction potential by training a neural network on a set of density functional theory calculations performed on configurations generated in multithermal-multibaric simulations. Here we show that the relative equilibrium between liquid gallium, alpha-Ga, beta-Ga, and Ga-II is well described. The resulting phase diagram is in agreement with the experimental findings. The local structure of liquid gallium and its nucleation into alpha-Ga and beta-Ga are studied. We find that the formation of metastable beta-Ga is kinetically favored over the thermodinamically stable alpha-Ga. Finally, we provide insight into the experimental observations of extreme undercooling of liquid Ga.