  In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a
minimum-cut in a (weighted) graph in time $O(m\log^3n)$ which he termed
near-linear time meaning linear (in the size of the input) times a
polylogarthmic factor. In this paper, we give the first deterministic algorithm
which runs in near-linear time for weighted graphs.
  Previously, the breakthrough results of Kawarabayashi and Thorup [KT19] gave
a near-linear time algorithm for simple graphs. The main technique here is a
clustering procedure that perfectly preserves minimum cuts. Recently, Li [Li21]
gave an $m^{1+o(1)}$ deterministic minimum-cut algorithm for weighted graphs;
this form of running time has been termed "almost-linear''. Li uses
almost-linear time deterministic expander decompositions which do not perfectly
preserve minimum cuts, but he can use these clusterings to, in a sense,
"derandomize'' the methods of Karger.
  In terms of techniques, we provide a structural theorem that says there
exists a sparse clustering that preserves minimum cuts in a weighted graph with
$o(1)$ error. In addition, we construct it deterministically in near linear
time. This was done exactly for simple graphs in [KT19, HRW20] and with
polylogarithmic error for weighted graphs in [Li21]. Extending the techniques
in [KT19, HRW20] to weighted graphs presents significant challenges, and
moreover, the algorithm can only polylogarithmically approximately preserve
minimum cuts. A remaining challenge is to reduce the
polylogarithmic-approximate clusterings to $1+o(1/\log n)$-approximate so that
they can be applied recursively as in [Li21] over $O(\log n)$ many levels. This
is an additional challenge that requires building on properties of
tree-packings in the presence of a wide range of edge weights to, for example,
find sources for local flow computations which identify minimum cuts that cross
clusters.
