Solução por Roger Benet, comentário de João Guilherme
Temos um problema comum de Floyd-Warshall. No caso tudo o que precisamos fazer é ler as arestas, rodar um floyd-warshall e depois procurar quem tem a menor maior distância, depois imprimimos essa distância.
O código que será demonstrado usa N dijkstras em vez de um floyd-warshall, porém a ideia geral é a mesma e ambos passam no tempo.