Orcs

#include <bits/stdc++.h>
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define SZ(x) ((int)x.size())

const int INF = 1000000002;
int D[105][105], N, M, T;
using namespace std;

int main()
{
    cin >> T;

    f(tt,1,T)
    {
        cin >> N >> M;
        f(i,1,N) f(j,1,N) D[i][j] = INF;
        f(i,1,N) D[i][i] = 0;
        f(i,1,M)
        {
            int a,b,c;
            scanf("%d %d %d", &a, &b, &c);
            D[a][b] = min(D[a][b],c);
            D[b][a] = min(D[b][a],c);
        }
        f(k,1,N) f(i,1,N) f(j,1,N) D[i][j] = min(D[i][j], D[i][k]+D[k][j]);
        int ans = INF;
        f(i,6,N)
        {
            unordered_set<int> s;

            f(p,1,5) s.insert(D[i][p]);
            if(s.find(INF) != s.end()) continue;
            if(SZ(s) != 1) continue;

            int far = 0;
            f(j,1,N) far = max(far, D[i][j]);
            ans = min(ans,far);
        }

        if(ans < INF) cout << "Map " << tt << ": " << ans << "\n";
        else cout << "Map " << tt << ": -1\n";
    }
}