The ultra-long period Cepheids (ULPCs) are classical Cepheids with pulsation periods exceeding $approx 80$ days. The intrinsic brightness of ULPCs are ~1 to ~3 mag brighter than their shorter period counterparts. This makes them attractive in future distance scale work to derive distances beyond the limit set by the shorter period Cepheids. We have initiated a program to search for ULPCs in M31, using the single-band data taken from the Palomar Transient Factory, and identified eight possible candidates. In this work, we presented the VI-band follow-up observations of these eight candidates. Based on our VI-band light curves of these candidates and their locations in the color-magnitude diagram and the Period-Wesenheit diagram, we verify two candidates as being truly ULPCs. The six other candidates are most likely other kinds of long-period variables. With the two confirmed M31 ULPCs, we tested the applicability of ULPCs in distance scale work by deriving the distance modulus of M31. It was found to be $mu_{M31,ULPC}=24.30pm0.76$ mag. The large error in the derived distance modulus, together with the large intrinsic dispersion of the Period-Wesenheit (PW) relation and the small number of ULPCs in a given host galaxy, means that the question of the suitability of ULPCs as standard candles is still open. Further work is needed to enlarge the sample of calibrating ULPCs and reduce the intrinsic dispersion of the PW relation before re-considering ULPCs as suitable distance indicators.