Introduction to algorithms class. Please show your work. And please do not copy any solutions to this problem that may already exist on Chegg Study.

You are given a directed graph G with (possibly negative) weighted edges, and a tree T defined using a subset of the edges of G. T is promised to have exactly one path from a vertex s to every other vertex in the graph. Give an O(m + n) time algorithm to decide whether or not T is a valid shortest path tree for G