In java, implement a graph data structure and calculate a shortest weighted path

You will need to read in a list of vertexes, edges, and weights (described below) and store them in either an adjacency list or matrix.

Based on the set of data you read in, you need to calculate a route with minimize the total cost of traveling between city 1 and city 2

Input/Output:

The first line is the number of cities (vertexes) N.

The second line of input are the number of roads (edges) M

The following N-2 lines are the motel prices at each city each as a single line. These lines consists of two numbers: the city number (3..N) and the motel cost (1..200).

The Last M lines of input are the gas prices for traveling between two cities on a given road, each expressed on a single line. These line consists of three numbers: city number (1..N), city number (3..N), cost of gas between the two cities (1..200).