#include<cstdio> #include<cstring> #define INF 0x3f3f3f3f using namespace std; //MST,prim //MST找最大权值 int matrix[505][505]; int dis[505]; bool vis[505]; int t,n,Min,tmp; void prim() { for(int i = 0; i<n; ++i) dis[i] = matrix[0][i]; vis[0] = 1; for(int i = 1; i<n; ++i) { Min = INF; for(int j = 1; j<n; ++j) { if(!vis[j]&&Min>dis[j]) { Min = dis[j]; tmp = j; } } vis[tmp] = 1; for(int i = 0; i<n; ++i) { if(!vis[i]&&dis[i]>matrix[tmp][i]) dis[i] = matrix[tmp][i]; } } tmp = 0; for(int i = 0; i<n; ++i) { if(tmp<dis[i]) tmp = dis[i]; } printf("%d\n",tmp); } int main() { scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i = 0; i<n; ++i) { for(int j = 0; j<n; ++j) scanf("%d",&matrix[i][j]); } prim(); } return 0; }