A building contractor is designing the ductwork for the heating and air conditioning system in a new, single$-$story medical building. The figure below summarizes the possible connections between the primary

air handling unit $($node $1)$ and the various air outlets to be placed in the building $($nodes $2$ through $9).$ The arcs in the network represent possible ductwork connections, and the values on the ares the

feet of ductwork required.

A graph with $9$ nodes and $19$ arcs is shown.

Node $1$ is connected to node $2$ by arc of value of $110,$ to node $3$ by arc of value of $100,$ to node $4$ by arc of value of $105,$ and to node $5$ by arc of value of $95.$

Node $2$ is connected to node $1$ by arc of value of $110,$ to node $3$ by arc of value of $45,$ to node $6$ by arc of value of $30,$ and to node $7$ by arc of value of $40.$

Node $3$ is connected to node $1$ by arc of value of $100,$ to node $2$ by arc of value of $45,$ to node $4$ by arc of value of $35,$ to node $6$ by arc of value of $50,$ to node $7$ by arc of value of $40,$ and to node $8$ by arc of value of $55.$

Node $4$ is connected to node $1$ by arc of value of $105,$ to node $3$ by arc of value of $35,$ to node $5$ by arc of value of $30,$ to node $7$ by arc of value of $45,$ and to node $9$ by arc of value of $50.$

Node $5$ is connected to node $1$ by arc of value of $95,$ to node $4$ by arc of value of $30,$ to node $8$ by arc of value of $46,$ and to node $9$ by arc of value of $55.$

Node $6$ is connected to node $2$ by arc of value of $30,$ to node $3$ by arc of value of $50,$ and to node $7$ by arc of value of $45.$

Node $7$ is connected to node $2$ by arc of value of $40,$ to node $3$ by arc of value of $40,$ to node $4$ by arc of value of $45,$ to node $6$ by arc of value of $45,$ and to node $8$ by arc of value of $45.$

Node $8$ is connected to node $3$ by arc of value of $55,$ to node $5$ by arc of value of $46,$ to node $7$ by arc of value of $45,$ and to node $9$ by arc of value of $35.$

Node $9$ is connected to node $4$ by arc of value of $50,$ to node $5$ by arc of value of $55,$ and to node $8$ by arc of value of $35.$

Starting at node $1,$ use the minimal spanning tree algorithm to determine how much ductwork should be installed to provide air access to each vent while requiring the least amount of ductwork.

How much ductwork $($in feet$)$ is required?

ft