Is it possible to reconstruct graph if we have given matrix of shortest pairs
I would suggest the following approach.

Maintain a data structure $H$ of $(i,j, g(i,j))$ triples so that you can efficiently find and remove a triple $(i,j,w)$ that minimises $w$.

Maintain a partition $P$ of nodes $V = \{1,2,\dotsc,N\}$.

Maintain a tree $T$.

We will maintain the invariant that $T$ contains some edges of the tree that we are trying to reconstruct, each part $X \in P$ is some subtree that we have not reconstructed yet. Eventually, $T$ will be the tree and $P$ will consist of singleton sets.

Initially, $P = \{V\}$ and $T = \emptyset$.

Apply the following operation repeatedly until $H$ is empty:


In $H$, find and remove a triple $(i,j,w)$ that minimises $w$.
See if $i$ and $j$ are in the same part of $P$. If not, discard this triple and try again.
Now we have a pair $(i,j)$ and a part $X \in P$ such that $i\in X$, $j \in X$. We now know that $\{i,j\}$ has to be an edge in the subtree induced by $X$.
Add $\{i,j\}$ to $T$.
For all nodes $v \in X$, see if $v$ is closer to $i$ or $j$. Based on this information, refine the partition $P$ by replacing $X$ with $X_i$ and $X_j$, where $X_i \subseteq X$ contains the nodes that are closer to $i$, and $X_j$ similarly.


If I am not mistaken, the time complexity is roughly as follows, assuming appropriate data structures:


We extract $O(N^2)$ triples.
Only $O(N)$ triples will result in something added to $T$. These are the triples that require nontrivial work.
For nontrivial triples, the operation that dominates is splitting. There we will need to check in the worst case $O(N)$ nodes.
So overall the running time is something like $O(N^2) + O(N) O(N) = O(N^2)$.
On top of this we pay whatever time we used to construct $H$. A simple solution is to just sort the triples $(i,j,w)$ by $w$. The cost depends on what kind of $w$ values you might have, but it isn't much worse than $O(N^2)$.