道を変える案.

const solution = (n, cities) => {
  cities.sort((a, b) => a[2] - b[2]);

  const parents = Array(n + 1);
  for (let i = 0; i < n + 1; i++) {
    parents[i] = i;
  }

  const findParent = x => {
    if (x === parents[x]) {
      return x;
    }
    return (parents[x] = findParent(parents[x]));
  };

  const unionParents = (a, b) => {
    a = findParent(a);
    b = findParent(b);

    if (a < b) {
      parents[b] = a;
    } else {
      parents[a] = b;
    }
  };

  const tree = Array(n + 1);
  for (let i = 0; i < n + 1; i++) {
    tree[i] = [];
  }

  for (const [a, b, weight] of cities) {
    if (findParent(a) !== findParent(b)) {
      tree[a].push([b, weight]);
      tree[b].push([a, weight]);
      unionParents(a, b);
    }
  }

  const findFarthestNode = start => {
    let farthestNode = null;
    let distance = 0;

    const visited = Array(n + 1).fill(false);
    visited[start] = true;
    const q = [[start, 0]];
    visited[start] = true;

    while (q.length) {
      const [curr, dist] = q.shift();

      if (dist > distance) {
        farthestNode = curr;
        distance = dist;
      }

      for (const [next, cost] of tree[curr]) {
        if (!visited[next]) {
          q.push([next, dist + cost]);
          visited[next] = true;
        }
      }
    }

    return farthestNode;
  };

  const farthestNode1 = findFarthestNode(1);
  const farthestNode2 = findFarthestNode(farthestNode1);

  const getRoute = (start, destination) => {
    const visited = Array(n + 1).fill(false);
    const q = [[start, 0]];
    visited[start] = true;

    while (q.length) {
      const [curr, dist] = q.shift();

      if (curr === destination) {
        return dist;
      }

      for (const [next, cost] of tree[curr]) {
        if (!visited[next]) {
          q.push([next, dist + cost]);
          visited[next] = true;
        }
      }
    }
  };

  const treeDistance = getRoute(farthestNode1, farthestNode2);

  const graph = Array(n + 1);
  for (let i = 0; i < n + 1; i++) {
    graph[i] = [];
  }
  for (const [a, b, weight] of cities) {
    graph[a].push([b, weight]);
    graph[b].push([a, weight]);
  }

  const dijkstra = (start, destination) => {
    const dist = Array(n + 1).fill(Infinity);
    const visited = Array(n + 1).fill(false);

    const getSmallestNode = () => {
      let value = Infinity;
      let index = 0;

      for (let i = 1; i <= n; i++) {
        if (!visited[i] && dist[i] < value) {
          value = dist[i];
          index = i;
        }
      }

      return index;
    };

    dist[start] = 0;
    visited[start] = true;

    for (const [to, cost] of graph[start]) {
      dist[to] = Math.min(dist[to], cost);
    }

    for (let i = 0; i < n - 1; i++) {
      const curr = getSmallestNode();
      visited[curr] = true;

      for (const [to, cost] of graph[curr]) {
        dist[to] = Math.min(dist[to], dist[curr] + cost);
      }
    }
    return dist[destination];
  };

  const graphDistance = dijkstra(farthestNode1, farthestNode2);

  return treeDistance - graphDistance;
};