We have investigated the poorly-understood origin of nitrogen in the early Galaxy by determining N abundances in 35 extremely metal-poor halo giants (22 stars have [Fe/H]<-3.0) using the C and O abundances determined in Paper V. Because any dredge-up of CNO processed material to the surface may complicate the interpretation of CNO abundances in giants, we have also measured the surface abundance of lithium. Our sample shows a clear dichotomy between two groups of stars. The first group shows evidence of C to N conversion through CN cycling and strong Li dilution, a signature of mixing. The second group shows no evidence for C to N conversion, and Li is only moderately diluted, and we conclude that their C and N abundances are very close to those of the gas from which they formed in the early Galaxy. These unmixed stars reflect the abundances in the early Galaxy: the [C/Fe] ratio is constant (about +0.2 dex) and the [C/Mg] ratio is close to solar at low metallicity, favouring a high C production by massive zero-metal supernovae. The [N/Fe] and [N/Mg] ratios scatter widely. The larger values of these ratios define a flat upper plateau ([N/Mg]= 0.0, [N/Fe]= +0.1), which could reflect higher values within a wide range of yields of zero-metal Sne II. Alternatively, by analogy with the DLAs, the lower abundances ([N/Mg]= -1.1, [N/Fe]= -0.7) could reflect generally low yields from the first Sne II, the other stars being N enhanced by winds of massive Asymptotic Giant Branch (AGB) stars. At present it cannot be decided whether primary N is produced primarily in SNe II or in massive AGB stars, or in both. The stellar N abundances and [N/O] ratios are compatible with those found in Damped Lyman-alpha (DLA) systems.