Extra Credit $[23$ points$]$ Consider a weighted, undirected graph $G=(V,E),$ where $|V|=n$ and $|E|=m.$ You are tasked with solving the following problems:

$[18$ points$]$ For both MST and shortest path problems, analyze the efficiency of Kruskal's, Prim's, and Dijkstra's algorithms for:

A dense graph $($where $m$~~$n^2).$

A sparse graph $($where $m$~~$n).$

$[5$ points$]$ Provide insights on which algorithm performs better in each scenario and why.