For this assignment, you are to write a program which will take the description of a weighted directed acyclic graph from standard input and write to standard output two numbers measuring the graph. The program will need to compute (i) the length of the longest path from Node 1 to Node N, and (ii) the number of distinct paths from Node 1 to Node N that have the longest length found in part (i).

You may store the graph with either an adjacency list or an adjacency matrix. Your program should implement a linear time (i.e., O(n + m) if using an adjacency list and O(n 2 ) if using an adjacency matrix) algorithm and will be tested on very large graphs, so you cannot possibly list them all.

The first line of the input is a line containing two integers, N and M. N is the number of nodes the nodes are 1, 2, 3, . . . , Nand M is the number of edges. There follow M lines describing each edge. An edge description is a line containing three integers I J W, where I J (i.e., the edge from I to J) and W > 0. In your outputs, please output the texts of longest path: and number of longest paths: before the values you compute, respectively. See below.

input file inSample1.txt:

5 7

1 2 7

1 3 10

2 4 8

2 5 3

3 4 5

3 5 10

4 5 5

Expected output:

longest path: 20

number of longest paths: 3

You will need to use standard input. Do not pass in the name of the file as an argument - do not encode the name of your input file in your program.

You may want to consider the case where the graph is not connected or where there is no path from node 1 to node N.

Please use Python or C.