`distance_threshold` not respected in `AgglomerativeClustering` with sparse `connectivity`

### Describe the bug

When passing a sparse `connectivity` to `AgglomerativeClustering` constrained by a given `distance_threshold`, the current implementation may return a clustering not respecting this constraint.

This is at least true for the 'complete' and 'average' linkage criteria. I found the origin of the problem in [`linkage_tree`](https://github.com/scikit-learn/scikit-learn/blob/80598905e517759b4696c74ecc35c6e2eb508cff/sklearn/cluster/_agglomerative.py#L384), because I saw the only moment the inter-point distances were calculated was here:

https://github.com/scikit-learn/scikit-learn/blob/80598905e517759b4696c74ecc35c6e2eb508cff/sklearn/cluster/_agglomerative.py#L565-L568

So the only distance info we have is for connected points. Then, for `linkage='complete'`, in the situation where you have clustered together two neighbours A and B, and in the next step you consider aggregating C, which is B's neighbour but not A's, if `d(A, C) > distance_threshold` but at the same time `d(B, C)` is the minimum remaining distance (at the top of the heap), then C will be aggregated with these two.

Now I'm not sure at all on how to fix this properly. One option is to compute all pairwise distances in the connection matrix `A` when `A` and the heap `inertia` are initialised:

 https://github.com/scikit-learn/scikit-learn/blob/80598905e517759b4696c74ecc35c6e2eb508cff/sklearn/cluster/_agglomerative.py#L596-L604

or to somehow compute the ones needed on the fly when two nodes with different neighbourhoods are merged. Both solutions seem quite expensive though.

To give you some context, I encountered this while trying to do a spatial aggregation of administrative boundaries (England's LSOAs), in such a way that an indicator (let's say average income) does not vary too much within the aggregated regions. In this kind of geographic context, this is a rather common task, the [Ward variant](https://pysal.org/spopt/generated/spopt.region.WardSpatial.html#spopt.region.WardSpatial) is even implemented in the `pysal` package.

### Steps/Code to Reproduce

```python
import numpy as np
import pandas as pd
from sklearn.feature_extraction.image import grid_to_graph
from sklearn.cluster import AgglomerativeClustering

rng = np.random.RandomState(0)
n_samples = 100
conn = np.ones([n_samples, n_samples], dtype=bool)
# Add some random sparsity, 70% at most
masked = (rng.random((n_samples, 70)) * n_samples).astype(int)
for i, nbh in enumerate(masked):
    conn[i, nbh] = False
    conn[nbh, i] = False
X = rng.randn(n_samples, 1)
clustering = AgglomerativeClustering(
    n_clusters=None,
    distance_threshold=1,
    connectivity=conn,
    linkage='complete',
    affinity='l1',
)
clustering.fit(X)
df = pd.DataFrame({'labels': clustering.labels_, 'x': X.flatten()})
clustered_df = df.groupby("labels")["x"].agg(["min", "max"])

# This should be < distance_threshold
print((clustered_df['max'] - clustered_df['min']).max())
# 1.20248995732655
```

### Expected Results

A float lower than 1, meaning the linkage criterion was respected.

### Actual Results

1.20248995732655

### Versions

```shell
System:
    python: 3.9.13 | packaged by conda-forge | (main, May 27 2022, 16:56:21)  [GCC 10.3.0]
executable: /home/thomaslouf/.conda/envs/ses-ling/bin/python
   machine: Linux-4.15.0-144-generic-x86_64-with-glibc2.27

Python dependencies:
      sklearn: 1.1.1
          pip: 22.1.2
   setuptools: 62.3.2
        numpy: 1.22.4
        scipy: 1.8.1
       Cython: None
       pandas: 1.4.2
   matplotlib: 3.5.2
       joblib: 1.1.0
threadpoolctl: 3.1.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
         prefix: libopenblas
       filepath: /home/thomaslouf/.conda/envs/ses-ling/lib/libopenblasp-r0.3.20.so
        version: 0.3.20
threading_layer: pthreads
   architecture: Bulldozer
    num_threads: 32

       user_api: openmp
   internal_api: openmp
         prefix: libgomp
       filepath: /home/thomaslouf/.conda/envs/ses-ling/lib/libgomp.so.1.0.0
        version: None
    num_threads: 1
```

COMMENT:
Thank you for opening the issue. This does look like a bug where `distance_threshold` is not observed correctly when connectivity is provided and `linkage='complete'`.

@GaelVaroquaux What do you think about this issue?

Labels: Bug, module:cluster, Needs Investigation