$n=2$ 情况。由于 $n$ 非常小，考虑对 $m$ 一维分治。设当前分治区间为 $[l,r]$。$l=r$ 时是平凡的，不再赘述。当区间长度大于等于 $2$ 时，记区间中点 $p=\lfloor(l+r)/2\rfloor$，则任意一个左侧点走到右侧点一定需要经过 $(1,p)$ 或者 $(2,p)$。记 $a_u,A_u$ 分别表示从 $(1,p)$ 走到左/右侧点 $u$ 的最短路，$b_u,B_u$ 则表示 $(2,p)$，那么两点 $(u,v)$ 之间的最短路为 $\min(a_u+A_v,b_u+B_v)$。

• $a_u+A_v\le b_u+B_v$ 时，$a_u-b_u\le A_v-B_v$，是一个一维偏序，直接排序之后计数 $a,A$ 的贡献即可。
• $b_u+B_v < a_u+A_v$ 时同理。

由于 $n=2$ 所以区间内的最短路一定不会跑出区间，所以直接对区间内的点做即可，直接写个 Dijkstra 加上偏序，复杂度 $O(n \log^2 n)$。

$n=3$ 情况与前文 $n=2$ 情况的区别在于，区间 $[l,r]$ 内两点间的最短路可能会跑出区间。进一步地，注意到只有 $(1,i)$ 和 $(3,i)$ 之间会存在这种情况，最短路可能绕过 $(2,i)$，走成形如 $(1,i)\rightarrow\cdots\rightarrow(1,p)\rightarrow(2,p)\rightarrow(3,p)\rightarrow\cdots\rightarrow(3,i)$，所以我们对所有的 $i$ 预处理出绕路的路径长度，然后在这两个点之间直接连出该边即可。计算绕路路径长度可以用前缀和，复杂度线性。

其余部分与前文类似，当 $n=3$ 时，跨越中点的路径一定会经过 $(1,p),(2,p),(3,p)$ 中至少一个点，和上文类似地记 $a_u,A_u,b_u,B_u,c_u,C_u$ 为对应最短路长度，那么左右两点 $(u,v)$ 间最短路为 $\min(a_u+A_v,b_u+B_v,c_u+C_v)$。对最小值是谁分类讨论：

• $a_u+A_v\le b_u+B_v,a_u+A_v\le c_u+C_v$ 时，类似地移项得到 $a_u-b_u\le B_v-A_v \wedge a_u-c_u\le C_v-A_v$，所以是一个二维偏序，离散化之后用 BIT 计数计算 $a_u,A_v$ 的贡献。
• 其余情况同理，要考虑是否取等号的问题，避免重复计算。总共 $a,A,b,B,c,C$ 六元，我写了六个二维偏序，比较 dirty。

复杂度 2log。