The Value of Side Information in Shortest Path Optimization