DATA STRUCTURES IN C/ TREES

Please only use c language. (at the end of the question there will be an example of the problem for more details)

the question is:

If You want to travel, then you choose to travel by plane to another country, and there may be layovers along the way. Each edge comes with its corresponding ticket price.

calculate the following:

1) calculate the minimum cost from the starting point to the destination.

2. Determine the number of paths that yield the minimum cost (since the answer may be too

large, modulo 10^9 + 7)

3. Calculate the minimum number of flights to take while minimizing the cost

4. Calculate the maximum number of flights to take while minimizing the cost

The program needs to read its inputs let say input.txt in a text file and put the output in another textfile output.txt

for our input we have the following rules

and as output: produce one line of output for each input. and print four integers according to the problem statement

here is an input sample and output sample

input(reading it from the text file):

1

4 5

1 4 5

1 2 4

2 4 5

1 3 2

3 4 3

output(to a text file):

5 2 1 2

picture of the tree is an example and the other picture just explain how the inputs work

2. Number of path that yield minimum cost: 2 3. Minimum number of flights while minimizing the cost: 1 4. Maximum number of flights while minimizing the cost: '2 The first line of input gives the number of test cases, T(1T50). Then T test cases follow each described in the following way: 1. The first line contains two integers n(1n105) and m(1m2105) separated by spaces, which indicate the number of countries and the number of flights. 2. In the subsequent m lines, each line contain three integers s,t,c(1s,tn,1 c109) separated by spaces, which indicate there is a flight from country s to country t with cost c.1 and n represent your starting point and destination respectively. note: You may assume that there is a path from starting point to destination