{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e小 A 是社团里的工具人,有一天他的朋友给了他一个 $n$ 个点,$m$ 条边的正权连通无向图,要他计算所有点两两之间的最短路。\u003cbr\u003e\u003cbr\u003e作为一个工具人,小 A 熟练掌握着 floyd 算法,设 $w[i][j]$ 为原图中 $(i,j)$ 之间的权值最小的边的权值,若没有边则 $w[i][j]\u003d$无穷大。特别地,若 $i\u003dj$,则 $w[i][j]\u003d0$。\u003cbr\u003e\u003cbr\u003eFloyd 的 C++ 实现如下:\u003cbr\u003e\u003cbr\u003e```c++\u003cbr\u003efor(int k\u003d1;k\u0026lt;\u003dp;k++)\u003cbr\u003efor(int i\u003d1;i\u0026lt;\u003dn;i++)\u003cbr\u003efor(int j\u003d1;j\u0026lt;\u003dn;j++)\u003cbr\u003e\u0026nbsp;\u0026nbsp;w[i][j]\u003dmin(w[i][j],w[i][k]+w[k][j]);\u003cbr\u003e```\u003cbr\u003e\u003cbr\u003e当 $p\u003dn$ 时,该代码就是我们所熟知的 $floyd$,然而小 A 为了让代码跑的更快点,所以想减少 $p$ 的值。\u003cbr\u003e\u003cbr\u003e令 $D_{i,j}$ 为最小的非负整数 $x$,满足当 $p\u003dx$ 时,点 $i$ 与点 $j$ 之间的最短路被正确计算了。\u003cbr\u003e\u003cbr\u003e现在你需要求 $\\sum_{i\u003d1}^{n}\\sum_{j\u003d1}^{n}D_{i,j}$,虽然答案不会很大,但为了显得本题像个计数题,你还是需要将答案对 $998244353$ 取模后输出。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行一个正整数 $T(T\\leq 30)$ 表示数据组数\u003cbr\u003e\u003cbr\u003e对于每组数据:\u003cbr\u003e\u003cbr\u003e第一行两个正整数 $n,m(1\\leq n\\leq 1000,m\\leq 2000)$,表示点数和边数。\u003cbr\u003e\u003cbr\u003e保证最多只有 $5$ 组数据满足 $max(n,m)\u0026gt;200$ \u003cbr\u003e\u003cbr\u003e接下来 $m$ 行,每行三个正整数 $u,v,w$ 描述一条边权为 $w$ 的边 $(u,v)$,其中 $1\\leq w\\leq 10^9$"}},{"title":"Output","value":{"format":"HTML","content":"输出 $T$ 行,第 $i$ 行一个非负整数表示第 $i$ 组数据的答案"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n4 4\r\n1 2 1\r\n2 3 1\r\n3 4 1\r\n4 1 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}