Best graphic card for gigabyte G31 motherboard

It seems there are AGP and PCI-E variants of this board. I'll assume AGP with your Pentium 4.

You'll probably need to head to ebay. The radeon x700 is a great card, for gaming. A radeon 9250 would be about $5.

For a PCI-E slot, an HD4650 for $40 will be fine for you.

There are AGP versions? I didn't see any. Im going to assume PCI-E.

Cheap best card are kinda opposites. Best = $$$$. You can get a good bang for your buck, but that is all you can do. What Power Supply do you have? A 4870 is a good bang for the buck and is kinda in the middle of the road. I am assuming you will play games on it. If you want a DX11 card the 5750 is a good deal, but performs under a 4870, however uses less power and is DX11.