This does not answer the question fully, but is too long for a comment. I'll try to add more to the answer. Also the answer is a bit rough; it does not explain most of the terms. I will polish it when I get some free time.
First of all, the weighted graph must be a metric; i.e., it should satisfy symmetry ($D(u,v) = D(v,u)$), nonnegativity ($D(u,v) \geq 0$ with equality iff $u=v$), and triangle inequality ($D(u,v) \leq D(u,w)+D(w,v)$). The way the problem is set up, symmetry and nonnegativity come for free. So it suffices to check for triangle inequality (this can be done by brute force if $n$ is not too large).
Technically, the question you are asking can be phrased as:
Which metrics can be isometrically embedded in $\ell^2$?
My first answer is: not all. To see this, take a graph with $10$ vertices (say) with weights: $D(x,y)$ is $1$ if either $x$ or $y$ is the special vertex $v_1$; otherwise it is $2$. (This is known a Greek/British airline metric.) It is a fun exercise to show that this cannot be embedded in $\mathbb R^d$ for any dimension $d$.
I have to dig up a bit for a general criterion to decide this question.
Meanwhile, suppose that I told you that a particular metric can indeed be embedded in $\mathbb R^d$ for some $d$, possibly much larger than $n$. Then, somewhat remarkably, one can show that you can embed the $n$ points in $\mathbb R^n$ itself. This is ultimately related to the fact that every $n \times n$ Gram matrix $G$ has a representation $v_1, v_2, \ldots v_n \in \mathbb R^n$ (notice that the vectors live in an $n$ dimensional space) such that $G_{i,j} = \langle v_i, v_j \rangle$. Unfortunately, however, in many scenarios of interest, $n$ could be much larger than the minimum dimension $d$, so this statement by itself is not always useful.
Added: The "correct" upper bound here is $d = n-1$. The discrete metric on $n$ points cannot be embedded in less than $n-1$ dimensions, so this is the best possible bound, if we want a universal upper bound.
When I can get to this, I would like to add any known criteria to compute the minimum dimension needed. Also, possibly mention something about dimensionality reduction, aka Johnson-Lindenstrauss.