// Graph class representing the towns of Switzerland
class Graph {
  // Map from vertex to list of edges
  Map<Vertex, List<Edge>> adjacencyList;

  // Add an edge to the graph
  void addEdge(Vertex v1, Vertex v2, int weight) {
    // Add the edge to the adjacency list of v1
    List<Edge> edges = adjacencyList.get(v1);
    if (edges == null) {
      edges = new ArrayList<>();
      adjacencyList.put(v1, edges);
    }
    edges.add(new Edge(v2, weight));

    // Add the edge to the adjacency list of v2
    edges = adjacencyList.get(v2);
    if (edges == null) {
      edges = new ArrayList<>();
      adjacencyList.put(v2, edges);
    }
    edges.add(new Edge(v1, weight));
  }
}

// Vertex class representing a town in Switzerland
class Vertex {
  // The language spoken in the town
  Language language;

  // Constructor
  Vertex(Language language) {
    this.language = language;
  }
}

// Edge class representing a road between two towns in Switzerland
class Edge {
  // The destination vertex and the weight of the edge
  Vertex destination;
  int weight;

  // Constructor
  Edge(Vertex destination, int weight) {
    this.destination = destination;
    this.weight = weight;
  }
}

// Enum class representing the four languages spoken in Switzerland
enum Language {
  GERMAN, FRENCH, ITALIAN, ROMANSH
}

// Find the shortest hike that goes through at least one town speaking each of the four languages
int findShortestHike(Graph graph) {
  int shortestHike = Integer.MAX_VALUE; // Initialize the shortest hike to infinity

  // For each vertex in the graph
  for (Vertex v : graph.adjacencyList.keySet()) {
    // If the language spoken in town v is not one of the four languages we are looking for, continue to the next vertex
    if (v.language != Language.GERMAN && v.language != Language.FRENCH && v.language != Language.ITALIAN && v.language != Language.ROMANSH) {
      continue;
    }

    // For each of the other three languages we are looking for, perform a breadth-first search starting at vertex v to find the shortest path to a town speaking that language
    int germanPathLength = findShortestPath(graph, v, Language.GERMAN);
    int frenchPathLength = findShortestPath(graph, v, Language.FRENCH);
    int italianPathLength = findShortestPath(graph, v, Language.ITALIAN);

    // Let hikeLength be the sum of the lengths of the three shortest paths found in the previous step
    int hikeLength = germanPathLength + frenchPathLength + italianPathLength;

    // If hikeLength is less than shortestHike, set shortestHike to hikeLength
    if (hikeLength < shortestHike) {
      shortestHike =