一个有向图，N个点编号1~N。M条边，每条边有一个权值c。
点对 (i, j) 之间的最短路长度记为 $S_{ij}$。（若 ij 不连通，则$S_{ij}=-1$）
在所有点对（共有$N^2$对）中，输出 $S_{ij}$ 最大的点对。如果存在多个 $S_{ij}$ 最大的情况，则一次输出（按 i 的大小由小到大输出，i 相同时按 j 的大小由小到大输出）。
多组输入。第一行一个整数 t 表示数据组数 ($t\le 50$)
对于每组数据：
第一行两个正整数 N、M。($2\le N\le 200, 1\le M\le 1000$)
接下来 M 行，每行三个整数 a,b,c，表示 a b 之间有一条权值为c的边（$1\le a,b\le N,1\le c\le 10^3$）
对于每组输入，输出 $S_{ij}$ 最大的点对（可能不止一对）。每一对 i j 输出一行，用一个空格隔开，按 i 的大小由小到大输出，i 相同时按 j 的大小由小到大输出，
2
2 1
1 2 3
3 3
1 2 2
2 3 3
3 1 51 2
2 1