Flight Instructor on a training flight reported being unable to meet the minimum climb gradient on a departure procedure resulting in a low altitude alert from ATC.

Narrative

I am a CFI that was conducting the long IFR cross country with my instrument student. We made a flight plan leaving KPVU to ZZZ our home airport. We briefed our route prior to flight. We contacted salt lake approach for a clearance and cleared us to ZZZ with the instrument departure procedure (PROVO4) we briefed the departure and knew it was going to be close. We departed KPVU and started the DP. I noticed fairly soon that we were not making the required climb gradient for the departure. I then told ATC about not being able to meet the required climb gradient and was told I needed to maintain the climb gradient. I replied back to the best of my knowledge saying currently flying our best rate of climb. Which was fluctuating from 150-700 fpm. I then started to think of a plan because we were approaching rising terrain. ATC warned me of the terrain and I then asked for a 30 degree left turn for terrain. ATC replied I was below the min vectoring altitude and gave me a low altitude alert. I then replied to cancel IFR and I turned the aircraft back towards KPVU and told ATC that I was going to climb either over the airport or near it 'I forget my exact words' to 10;300 for the MEA required for the route and get a new clearance upon reaching 10300. I was then told by ATC that I needed to copy a phone number for a possible pilot deviation. Reflecting on this issue I now realized that I had a few other options I could have used. Departing VFR and picking up a clearance in the air because of the VFR conditions present. As well as taking into consideration that our calculated climb rate at the time was just enough to make the DP mins with not much of a buffer. Which later proved to not be satisfactory for the DP. I should have also canceled IFR right away once I noticed we were not making the climb gradient required.