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.
https://gist.github.com/jogu99/e8850c3fdb6cdaefef39c7c614400ea6