Graph Algorithms · Medium problem

A network connects towers $p,q,r,s,t$ with possible cables and costs $pq{:}5, pr{:}2, qr{:}3, qs{:}8, rs{:}4, rt{:}6, st{:}1$. If cable $rs$'s cost rises from $4$ to $9$, by how much does the minimum total connection cost increase?