int floydMarshall(int **Adj){
  int k, i, j;
  for (k = 1; k <= nCities; k++){
    for (i = 1; i <= nCities; i++){
      for (j = 1; j <= nCities; j++){
        if (Adj[i][k] + Adj[k][j] < INFINITE && Adj[i][k] + Adj[k][j] < Adj[i][j])
          Adj[i][j] = Adj[i][k] + Adj[k][j];
      }
    }
  }
}