The following greedy algorithm should reconstruct the tree corresponding to a given distance matrix $M$, assuming it exists.

Beforehand, one must show that $T$, if it exists, is unique, but unless you insist I will skip these details
(informally, you can use induction on $n$: from a tree $T$ for $M$, remove a leaf $l$, use induction to get the unique tree for $M$ with the $l$ row/column removed, then show that there is only one unique place to plug back $l$).

Start with $F$ as the forest on $n$ vertices and no edge.

While $F$ is not a tree:

Choose $u$ and $v$ such that $u$ and $v$ are in two different
connected components of $F$ and $M_{u, v}$ is minimum among all
possible choices.

Add $uv$ to $F$ and set its weight to $M_{u, v}$

Suppose that we do not obtain a tree with distance matrix $M$ after running the algorithm, but that such a tree $T$ exists.

Let $uv$ be the first inserted (weighted) edge such that $uv$ does not belong to $T$ (observe that if $uv$ belongs to $T$, its weight must be correct).
Let $F$ be the forest obtained from the algorithm before inserting $uv$,
and for a vertex $x$,
denote by $C(x)$ the connected component of $F$ containing $x$.
Note that $C(u) \neq C(v)$.

Now, let $z$ be the
neighbour of $u$ on the path from $u$ to $v$ in $T$.
We have $d(u, v) = d(u, z) + d(v, z)$, implying $d(v, z) < d(u, v)$ (assuming strictly positive weights).
If $C(v) \neq C(z)$, the algorithm would have chosen the $vz$ edge instead of $uv$,
so assume $C(v) = C(z)$. But then, $C(u) \neq C(z)$ and $d(u, z) < d(u, v)$, again contradicting the choice of the algorithm. Therefore the $uv$ edge is correct.

Of course, there is no guarantee that the algorithm reflects the distances of $M$, but if that's the case, it means that no tree exists for $M$.