In java language

Design and implement a program to read information about roads connecting a set of cities and find the shortest path between two cities entered by the user.

Input File:

Input consists of information about the roads connecting the set of cities. The first line of input contains 2 integer M and N where indicated the number of cities and M the number of roads. The next M lines contain the description of the roads. Each road is described by 3 numbers S, D, L, where S and D are cities numbers and L is the distance between them.

Output:

A line containing the shortest distance to go from city S to D.

Sample input:

5 10

0 1 16

0 3 2

0 4 3.0

1 2 5

2 1 3

3 1 12

3 4 7

4 1 10

4 2 4

4 3 5

Sample output

The shortest distance between 0 and 1 is 10