Solomons Key?

Theres this game that i used to play for the family computer (NES), it was really enjoyable, the main thing i remember about it is that the game was called Mario 16(im pretty sure :s). I dont know if i was delusional or what but thats what i remember of the title. It is a sidescrolling platformer set in the prehistoric ages and each stage had end bosses that were dinosaurs, prehistoric plants, etc.. . The only weapon i remember was rolling donut shaped rocks. I rreally need this game because i think i spent 6 months tying to finish it but i could never get past the 3rd level whos end boss was a giant man eating plant. I want to beat this game now after all those years.