A new adaptive algorithm for penalty function optimization for minimum-energy three-states conical intersections (ME3CI) is suggested. The new algorithm differs from the original penalty function algorithm by (a) removing the redundancy in the target function, (b) using an adaptive increment for the penalty function weighting factor, and (c) using tighter convergence criteria for the energy gap. The latter was introduced to guarantee convergence to a true conical intersection rather than to a narrowly avoided crossing geometry. The new algorithm was tested in the optimization of the ME3CI geometries in butadiene and malonaldehyde, where all of the previously found true ME3CI geometries were recovered. The previously found butadiene's CI3/2/1 turned out to be a narrowly avoided crossing. For butadiene, seven new ME3CI geometries have been located. Because of the removal of the redundancy and the use of the adaptive weighting factor, the convergence rate of the new algorithm is noticeably improved as compared to that of the previously proposed penalty function algorithm. The application to malonaldehyde and butadiene demonstrates that the three-state conical intersections may be more abundant and hence more involved in the photochemistry than previously thought. The recently developed mixed-reference spin flip (MRSF)-TDDFT method yields ME3CI geometries and relative energies quantitatively consistent with the previously reported calculations at a much reduced computational cost.