  One-dependent first passage percolation is a spreading process on a graph
where the transmission time through each edge depends on the direct
surroundings of the edge. In particular, the classical iid transmission time
$L_{xy}$ is multiplied by $(W_xW_y)^\mu$, a polynomial of the expected degrees
$W_x, W_y$ of the endpoints of the edge $xy$, which we call the penalty
function. Beyond the Markov case, we also allow any distribution for $L_{xy}$
with regularly varying distribution near $0$. We then run this process on three
spatial scale-free random graph models: finite and infinite Geometric
Inhomogeneous Random Graphs, and Scale-Free Percolation. In these spatial
models, the connection probability between two vertices depends on their
spatial distance and on their expected degrees.
  We show that as the penalty-function, i.e., $\mu$ increases, the transmission
time between two far away vertices sweeps through four universal phases:
explosive (with tight transmission times), polylogarithmic, polynomial but
strictly sublinear, and linear in the Euclidean distance. The strictly
polynomial growth phase here is a new phenomenon that so far was extremely rare
in spatial graph models. The four growth phases are highly robust in the model
parameters and are not restricted to phase boundaries. Further, the transition
points between the phases depend non-trivially on the main model parameters:
the tail of the degree distribution, a long-range parameter governing the
presence of long edges, and the behaviour of the distribution $L$ near $0$. In
this paper we develop new methods to prove the upper bounds in all
sub-explosive phases. Our companion paper complements these results by
providing matching lower bounds in the polynomial and linear regimes.
