无向图最短路径问题，是图论中最经典也是最基础的问题之一。本题我们考虑一个有 \(n\) 个结点的无向图 \(G\)。

每一条边的边权是非负实数，但我们并不知道每一条边的具体边权。

本题中，每一组数据都有多次询问，每一次询问分别给出了一个无向图\(G\)。

输入的第一行是一个整数 \(t\)，表示总共的询问个数。之后依次给出每一次询问。

不难发现，因为给定的矩阵 \(d\) 中每一个数字都是整数，所以最大可能边权总会是整数。

注册一个 Vijos 通用账户，您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。