import java.util.*;

public class WeightedGraph<V> extends UnweightedGraph<V> {
  /** Tworzy pusty graf */
  public WeightedGraph() {
  }
  
  /** Tworzy graf ważony na podstawie wierzchołków i krawędzi podanych w tablicach */
  public WeightedGraph(V[] vertices, int[][] edges) {
    createWeightedGraph(java.util.Arrays.asList(vertices), edges);
  }

  /** Tworzy graf ważony na podstawie krawędzi podanych w tablicy i liczby wierzchołków */
  public WeightedGraph(int[][] edges, int numberOfVertices) {
    List<V> vertices = new ArrayList<>();
    for (int i = 0; i < numberOfVertices; i++)
      vertices.add((V)(new Integer(i)));
    
    createWeightedGraph(vertices, edges);
  }

  /** Tworzy graf ważony na podstawie list wierzchołków i krawędzi */
  public WeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
    createWeightedGraph(vertices, edges);
  }

  /** Tworzy graf ważony z wierzchołkami 0, 1, 2,… i listą krawędzi */
  public WeightedGraph(List<WeightedEdge> edges,
      int numberOfVertices) {
    List<V> vertices = new ArrayList<>();
    for (int i = 0; i < numberOfVertices; i++)
      vertices.add((V)(new Integer(i)));
    
    createWeightedGraph(vertices, edges);
  }

  /** Tworzy listy sąsiedztwa na podstawie tablicy krawędzi */
  private void createWeightedGraph(List<V> vertices, int[][] edges) {
    this.vertices = vertices;     

    for (int i = 0; i < vertices.size(); i++) {
      neighbors.add(new ArrayList<Edge>()); // Tworzenie listy wierzchołków
    }

    for (int i = 0; i < edges.length; i++) {
      neighbors.get(edges[i][0]).add(
        new WeightedEdge(edges[i][0], edges[i][1], edges[i][2]));
    }
  }

  /** Tworzy listy sąsiedztwa na podstawie list krawędzi */
  private void createWeightedGraph(
      List<V> vertices, List<WeightedEdge> edges) {
    this.vertices = vertices;     

    for (int i = 0; i < vertices.size(); i++) {
      neighbors.add(new ArrayList<Edge>()); // Tworzenie listy wierzchołków
    }

    for (WeightedEdge edge: edges) {      
      neighbors.get(edge.u).add(edge); // Dodawanie krawędzi do listy
    }
  }

  /** Zwraca wagę krawędzi (u, v) */
  public double getWeight(int u, int v) throws Exception {
    for (Edge edge : neighbors.get(u)) {
      if (edge.v == v) {
        return ((WeightedEdge)edge).weight;
      }
    }
    
    throw new Exception("Krawędź nie istnieje");
  }
  
  /** Wyświetla krawędzie z wagami */
  public void printWeightedEdges() {
    for (int i = 0; i < getSize(); i++) {
      System.out.print(getVertex(i) + " (" + i + "): ");
      for (Edge edge : neighbors.get(i)) {
        System.out.print("(" + edge.u +
          ", " + edge.v + ", " + ((WeightedEdge)edge).weight + ") ");
      }
      System.out.println();
    }
  }
 
  /** Dodaje krawędź do grafu ważonego */
  public boolean addEdge(int u, int v, double weight) {
    return addEdge(new WeightedEdge(u, v, weight));
  }

  /** Pobiera drzewo MST z korzeniem w wierzchołku 0 */
  public MST getMinimumSpanningTree() {
    return getMinimumSpanningTree(0);
  }
  
  /** Pobiera drzewo MST z korzeniem w podanym wierzchołku */
  public MST getMinimumSpanningTree(int startingVertex) {
    // cost[v] przechowuje koszt dodania v do drzewa
    double[] cost = new double[getSize()];
    for (int i = 0; i < cost.length; i++) {
      cost[i] = Double.POSITIVE_INFINITY; // Początkowy koszt
    }
    cost[startingVertex] = 0; // Koszt dla wierzchołka źródłowego to 0

    int[] parent = new int[getSize()]; // Rodzic wierzchołka 
    parent[startingVertex] = −1; // Wierzchołek startingVertex jest korzeniem
    double totalWeight = 0; // Dotychczasowa suma wag

    List<Integer> T = new ArrayList<>();
    
    // Powiększanie T
    while (T.size() < getSize()) {
      // Znajdowanie w V − T wierzchołka u o najniższym koszcie
      int u = −1; // Szukany wierzchołek
      double currentMinCost = Double.POSITIVE_INFINITY;
      for (int i = 0; i < getSize(); i++) {
        if (!T.contains(i) && cost[i] < currentMinCost) {
          currentMinCost = cost[i];
          u = i;
        }
      }

      if (u == -1) break; else T.add(u); // Dodawanie nowego wierzchołka do T
      totalWeight += cost[u]; // Dodawanie cost[u] do sumy

      // Dostosowanie cost[v] dla v sąsiadującego z u i należącego do V − T
      for (Edge e : neighbors.get(u)) {
        if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) {
          cost[e.v] = ((WeightedEdge)e).weight;
          parent[e.v] = u; 
        }
      }
    } // Koniec pętli while

    return new MST(startingVertex, parent, T, totalWeight);
  }

  /** MST jest klasą wewnętrzną w klasie WeightedGraph */
  public class MST extends SearchTree {
    private double totalWeight; // Łączna waga wszystkich krawędzi drzewa

    public MST(int root, int[] parent, List<Integer> searchOrder,
        double totalWeight) {
      super(root, parent, searchOrder);
      this.totalWeight = totalWeight;
    }

    public double getTotalWeight() {
      return totalWeight;
    }
  }

  /** Znajduje najkrótsze ścieżki z jednego źródła */
  public ShortestPathTree getShortestPath(int sourceVertex) {
    // cost[v] przechowuje koszt ścieżki z v do źródła
    double[] cost = new double[getSize()];
    for (int i = 0; i < cost.length; i++) {
      cost[i] = Double.POSITIVE_INFINITY; // Początkowo koszt jest ustawiany na nieskończoność
    }
    cost[sourceVertex] = 0; // Koszt dla źródła jest równy 0

    // parent[v] przechowuje wierzchołek będący poprzednikiem v w ścieżce
    int[] parent = new int[getSize()];
    parent[sourceVertex] = -1; Rodzicowi źródła przypisywana jest wartość −1
    
    // T przechowuje wierzchołki, dla których znaleziono już ścieżkę
    List<Integer> T = new ArrayList<>();
    
    // Powiększanie T
    while (T.size() < getSize()) {
      // Znajdowanie wierzchołka u o najniższym koszcie w V − T 
      int u = -1; // Szukany wierzchołek
      double currentMinCost = Double.POSITIVE_INFINITY;
      for (int i = 0; i < getSize(); i++) {
        if (!T.contains(i) && cost[i] < currentMinCost) {
          currentMinCost = cost[i];
          u = i;
        }
      }
      
      if (u == -1) break; else T.add(u); // Dodawanie nowego wierzchołka do T
      
      // Dostosowanie cost[v] na podstawie v sąsiadującego z u i należącego do V − T
      for (Edge e : neighbors.get(u)) {
        if (!T.contains(e.v) 
            && cost[e.v] > cost[u] + ((WeightedEdge)e).weight) {
          cost[e.v] = cost[u] + ((WeightedEdge)e).weight;
          parent[e.v] = u; 
        }
      }
    } // Koniec pętli while

    // Tworzenie drzewa typu ShortestPathTree
    return new ShortestPathTree(sourceVertex, parent, T, cost);
  }

  /** ShortestPathTree jest klasą wewnętrzną w klasie WeightedGraph */
  public class ShortestPathTree extends SearchTree {
    private double[] cost; // cost[v] to koszt ścieżki z v do źródła

    /** Konstruktor ShortestPathTree */
    public ShortestPathTree(int source, int[] parent, 
        List<Integer> searchOrder, double[] cost) {
      super(source, parent, searchOrder);
      this.cost = cost;
    }

    /** Zwraca koszt ścieżki z korzenia do wierzchołka v */
    public double getCost(int v) {
      return cost[v];
    }

    /** Wyświetla ścieżki z wszystkich wierzchołków do źródła */
    public void printAllPaths() {
      System.out.println("Wszystkie najkrótsze ścieżki z " +
        vertices.get(getRoot()) + ":");
      for (int i = 0; i < cost.length; i++) {
        printPath(i); // Wyświetlanie ścieżki ze źródła i do niego
        System.out.println("(koszt: " + cost[i] + ")"); // Koszt ścieżki
      }
    }
  }
}