In this assignment, you will help a transportation company. There will be a main office of the company and a number of branch offices. The main office wants to deliver some goods to other offices, so for each branch, a truck goes out from main office. Company knows the distances between the offices and wants to use the shortest path toward each office to reduce their costs. Your program will find the shortest paths from main office to each branch offices.

Your program will read the number of offices and the distance matrix from a text file as in he following sample input file.

First row indicates the distance from 0th office to offices 0,1,2,3,4, respectively. Second row similarly indicates the distance from 1st office to offices 0,1,2,3,4, respectively and so forth. If there is a connection from x to y with a distance of d> 0 then you should set M[x][y] = d If there is no connection, -1 is provided as an entry, then M[x][y] = -1

**Main office**

Everyone will use his/her university id number’s first 2 and last 3 digits as the seed for the random number generator. If your id is 990702003 then you will use 99003 as the seed. Random number generator will decide which office will be considered as the main office and your algorithm will execute accordingly.

**Output File
**Example: Main office is randomly determined as “0”, then following output file must be generated:

Solution :