Code in C++

Descriptions: Let T be a tree with root v. The edges of T are undirected. Edge in T has a nonnegative length. Write a C++ function to determine the length of the shortest paths from v to the remaining vertices of T. Your function should have complexity O(n), where n is the number of vertices in T. Show that this is the case. Input Format: The input describes a tree topology in a graph way. The first line of the input is a number V. It represents the vertices count. Each vertex has one id, it ranges from 1 to V. The rest of the input contains V 1+1 lines. For the first V 1 lines, ecah line consists of three numbers s, t and c. It describes a edge between s vertex and t vertex in this undirected graph. The last line of input consists of one number v, which represents the root of the tree. You are going to calculate the shortest path to each tree child node from here. C Output Format: The output consists of V lines. Each line i consists of two numbers i and Ci. i represnet the index of vertex i. Ci represents the cost to walk from vertex v to this vertex i. Technical Specification: The graph in input has no cycle. Tree definition, Vv,u E T, there is only one path to connect v and u. 1