Ultimate Weapon
You probably have encountered Ultimate Weapon many times in the game. Its the big, black, robot like beast which attacks Mideel. After that attack it flies away and roams over the world map. Normally you do not have to kill it to finish the game. But since you want Cloud's best weapon (Ultima). You can also Steal from him Cursed Ring.
Although Ultimate Weapon is the easiest of the weapons he still could be still a pretty tricky fight if not equipped properly or not knowing where he has flown of next; Ok I have to admit I missed Cloud's best Weapon in my first game through FF7, but now I have it since I started again.
Ultimate Weapon is the black creature who attacked Mideel. When its hovering over near Cosmo Canyon, bump into him with the Highwind. The game automatically puts you in Battle Mode. Ultimate Weapon will attack with its normal weapon several times and sometimes with its super weapon. Try to heal as much as possible and use the most powerful magic you have on him (Like Ultima and Bahamut ZERO).
It will eventually fly away and roam the world again. Keep bumping into him and he will stop and hover somewhere. You'll have to repeat this several time until he stops between Cosmo Canyon & The Ancient Forest (Also Known as Frog Forest) . Fight him again and after his "ShadowFlare" (It's an Enemy Skill) he usually dies and falls onto the mountains. Now you can walk to the Ancient Forest and get cool stuff without a Green, Black or Gold Chocobo To get there.
Ultimate Weapon is rather simple to kill compared with say Ruby or Emerald & So far a haven't made up a straterg to kill but if to popular Demand I will make one.