Can we make distances in a finite subset of a manifold whatever we want? Given a connected smooth manifold $M$ of dimension $m>1$, points $p_1,\dots,p_n\in M$ and positive values $\{d_{i,j};1\leq i<j\leq n\}$ satisfying the strict triangle inequalities $d_{i,j}<d_{i,k}+d_{k,j}$,
Can we give $M$ a complete riemannian metric $g$ so that $d_g(p_i,p_j)=d_{i,j}$, where $d$ is the geodesic distance?
This can fail in dimension $2$, as shown in the answer by André Henriques. I'm pretty sure it has to be true for $m\geq3$, but I have not been able to prove it.
Some comments:

*

*This occurred to me while answering Equidistant points on a compact Riemannian manifold, my answer to that question contains the ideas I tried for $m\geq3$.


*By homogeneity of manifolds you can suppose the points $P_1,\dotsc,P_n$ are any set of $n$ points of $M$, and using that it is not hard to reduce the problem to the case of $M$ being diffeomorphic to $\mathbb{R}^m$. In particular if you prove it for $\mathbb{R}^3$ you will have proved it for any manifold of dimension $\geq 3$.


*One of the first ideas which come to mind is trying to somehow imbed $M$ in $\mathbb{R}^N$ for some big $N$, but triangle inequalities are not sufficient for a finite set to be isometrically imbedded in some $\mathbb{R}^N$.


*What if we change the strict triangle inequalities for the usual ones?
 A: Yes if $m\ge 2$.
Let us construct a metric graph $\Gamma$ by connecting vertices $p_1,\dots,p_n$ by edges with lengths $m_{ij}$.
Take its tiny tubular neighborhood and observe its surface has a nearly isometric copy of $\Gamma$; the edges are assumed to be minimizing.
We can also assume that embedding is stretching all edges slightly.
We may assume that each edge runs in a flat part so by conformal change, we can make $\Gamma$ isometric.
A: It is not possible to find $5$ points $x_1,\ldots,x_5$ on a genus zero Riemannian 2-manifold (a sphere) such that $d(x_i,x_j)=1$ for all $i,j$.
The reason is that the complete graph $K_5$ is not planar.
Assume by contradiction that we have $5$ points $x_1,\ldots,x_5$ with  $d(x_i,x_j)=1$.
Up to permuting the points, we may assume that the minimal geodesic connecting $x_1$ and $x_3$ crosses the minimal geodesic connecting $x_2$ and $x_4$.
Let $y$ be the point at which these two geodesics intersect.
Then
\begin{align*}
2&=d(x_1,x_3)+d(x_2,x_4)\\
&=d(x_1,y)+d(y,x_3)+d(x_2,y)+d(y,x_4)\\
&=\tfrac12\big((d(x_1,y)+d(y,x_2))\\
&\qquad(d(x_2,y)+d(y,x_3))+\\
&\qquad(d(x_3,y)+d(y,x_4))+\\
&\qquad(d(x_4,y)+d(y,x_1))
\big)\\
&\ge\tfrac12\big(d(x_1,x_2)+d(x_2,x_3)+d(x_3,x_4)+d(x_4,x_1)\big)=2
\end{align*}
with equality iff $y$ lies on all six geodesics (between $x_i$ and $x_j$ $\forall i,j\in\{1,2,3,4\})$. But if $y$ lies on all six geodesics, then these six geodesics are all part of a single geodesic line (i.e. the points are "aligned"), which is clearly impossible.
The crucial thing that I'm using here is the fact that geodesics admit unique extensions. If the ambient space was a graph, then my argument for deriving a contradiction wouldn't work as I wouldn't be able to conclude that the points are "aligned".

In higher dimensions, the answer is yes.
Take the complete graph $K_n$ on your set of points. Embed it in $M$. Then put a metric on $M$ that agrees with your desired metric in a neighbourhood of the graph, and which is extremely huge away from the graph. Then minimal geodesics will essentially follow the graph.
This solves the problem "up to $\varepsilon$", as the geodesics don't exactly follow the graph, but do so only approximately.
To finish the argument, do the same thing in families, and invoke some version of the intermediate value theorem.
Here's how the argument goes. Let $D$ be the space of metrics on your fixed finite set.
Instead of doing the above construction  for a single choice $d\in D$ of distances between the points $x_i$, imagine that we adapt it to instead construct a family of Riemannian metrics on $M$ parametrised by the space $D$. Starting from $d\in D$, the geodesic distance between the $x_i$ produces another element $d'\in D$. So we get a self-map $D\to D$ which is $\varepsilon$-away from the identity map on $D$. Now, $D$ is itself a manifold, and any self-map that's $\varepsilon$-away from the identity is surjective.
[added later: the answer is no]
Error in the above argument: $D$ is in fact a manifold with boundary. My argument works for metrics $d\in D\setminus \partial D$. I.e., metrics where the triangle inequality holds strictly.
A counterexample is provided by the metric on $\{x_1,x_2,x_3,x_4\}$ given by
$d(x_1,x_i)=1$, $d(x_i,x_j)=2$ (where $i,j\in\{2,3,4\}$)
[added even later: all is good] Ha ha! I hadn't noticed that you had assumed the strict triangle inequality to hold. So all is good, and this is a valid argument.
