complete task 1 , 2 , 3 and 4 in the code Below:

def graph_input(): # taking the graph input here lines = input() lines = lines.strip().split(' ') # N denotes node, E denotes E N = int(lines[0]) E = int(lines[1]) # the adjacency matrix, e,g: if I can go to node 2 from node 1, # I can have this in adj_mat adj_mat[1]: [2] adj_mat = {} # the weight matrix, e,g: if I can go to node 2 from node 1 with edge weight 10, # I can have this in the weight_matrix, weight_mat[1]: [10] weight_mat = {} # weight matrix for i in range(0, E): """ # Task 1: Take the graph input here and store it in adj_mat and weight matrix - Take 3 inputs a, b, c, denoting from a you can go to b having an edge of weight c - The graph will be undirected so using the same edge you can go to b from a and vice versa - Need to store both edge and weight """ # taking input of root node and saving it as in integer number root_node = int(input().strip()) return root_node, N, E, adj_mat, weight_mat def recursion_dfs(n=None, adj_mat={}, weight_mat={}, parent={}): # n: current node # adj_mat: adjacency matrix # weight_mat: weight_matrix # parent: parent information will be saved into a dictionary # recursive dfs function min_cost = None # minimum cost observed, Minimum weight that is observed in any path from node n best_leaf_node = None # the child node in which path, I am getting the minimum for i in range(0, len(adj_mat[n])): child = adj_mat[n][i] # ith child weight = weight_mat[n][i] """ # Task 2 & 3: Apply DFS, calculate the minimum weighted/costed path and the child in which path I am getting the minimum - Check should we need to go to child node or not, if child node is parent of n, then we will not go. otherwise we shall go to that node - Call the recursive function - return the minimum cost that is observed across in any path - store the minimum cost along with the last leaf node that is giving the result """ if min_cost is not None: # returning the minimum value observed across any path along with the child node's index that gives the result return min_cost, best_leaf_node else: # reached leaf node, no more cost to add, base case # returning 0 cost and the last leaf node return 0, n def print_path(parent, last_leaf_node): current = last_leaf_node while current is not None: # loop will continue until all the nodes from the leaf to root are not printed print(current) """ Task 4: print the path from last_leaf_node to root node that gives the least cost in the graph """ def dfs_algorithm(N, E, adj_mat, weight_mat, root_node): # We are going to implement DFS algorithm in recursive form parent = {} # a dictionary to store the parent of each node observed during traversal parent[root_node] = None # root node does not have any parent min_cost, best_leaf_node = recursion_dfs(n=root_node, adj_mat=adj_mat, weight_mat=weight_mat, parent=parent) print_path(parent=parent, last_leaf_node=best_leaf_node) return if __name__ == "__main__": root_node, N, E, adj_mat, weight_mat = graph_input() dfs_algorithm(N, E, adj_mat, weight_mat, root_node)