  The \emph{maximal $k$-edge-connected subgraphs} problem is a classical graph
clustering problem studied since the 70's. Surprisingly, no non-trivial
technique for this problem in weighted graphs is known: a very straightforward
recursive-mincut algorithm with $\Omega(mn)$ time has remained the fastest
algorithm until now. All previous progress gives a speed-up only when the graph
is unweighted, and $k$ is small enough (e.g.~Henzinger~et~al.~(ICALP'15),
Chechik~et~al.~(SODA'17), and Forster~et~al.~(SODA'20)).
  We give the first algorithm that breaks through the long-standing
$\tilde{O}(mn)$-time barrier in \emph{weighted undirected} graphs. More
specifically, we show a maximal $k$-edge-connected subgraphs algorithm that
takes only $\tilde{O}(m\cdot\min\{m^{3/4},n^{4/5}\})$ time. As an immediate
application, we can $(1+\epsilon)$-approximate the \emph{strength} of all edges
in undirected graphs in the same running time.
  Our key technique is the first local cut algorithm with \emph{exact}
cut-value guarantees whose running time depends only on the output size. All
previous local cut algorithms either have running time depending on the cut
value of the output, which can be arbitrarily slow in weighted graphs or have
approximate cut guarantees.
