Data Procurement for Shortest Paths on Random Graphs