#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

/*
    Keep your solution for Prim's algorithm Part in this file!
    Program Compile Command: g++ -std=c++11 -Wall -Werror prim.cpp -o prim
    Program Run Command: ./prim <input.txt>
    Expected input: /cases/case{$n}/input{$n}.txt
    Expected output: prim.txt
    Please, try to write clean and readable code. Remember to comment!!
*/

const string OUTPUT_FILE = "prim.txt";
const string BAKERY_ROAD_SEPARATOR = "->";

struct City {
    int x;
    int y;
    int pount;
};

struct Edge {
    int source;
    int destination;
    int weight;
};

struct Graph
{
    int number_of_cities;
    int number_of_bakeries;
    float threshold;

    vector<int> bakery_source_indices;
    vector<City> cities;
    vector<Edge> edges;

    void calculate_edges()
    {
        edges.clear();

        for (int i = 0; i < number_of_cities; i++)
        {
            for (int j = i + 1; j < number_of_cities; j++)
            {
                int plow = abs(cities[i].pount - cities[j].pount);
                float mean_pount = (cities[i].pount + cities[j].pount) / 2.0;

                if (0 < plow && plow <= threshold * mean_pount)
                {
                    edges.push_back({i, j, plow});
                }
            }
        }
    }

    void read(std::istream &input)
    {
        input >> number_of_cities;
        input >> number_of_bakeries;
        input >> threshold;

        bakery_source_indices.resize(number_of_bakeries);
        for (auto &bakery_index : bakery_source_indices)
        {
            input >> bakery_index;
        }

        cities.resize(number_of_cities);
        for (auto &city : cities)
        {
            input >> city.x >> city.y >> city.pount;
        }
    }

    // Print the graph to the given output stream
    // This function is used for debugging purposes
    void print(std::ostream &out)
    {
        out << "Number of cities: " << number_of_cities << endl;
        out << "Number of bakeries: " << number_of_bakeries << endl;
        out << "Threshold: " << threshold << endl;

        out << "Bakery indices: ";
        for (auto bakery_index : bakery_source_indices)
        {
            out << bakery_index << " ";
        }
        out << endl;

        out << "Cities: " << endl;
        for (auto city : cities)
        {
            out << city.x << " " << city.y << " " << city.pount << endl;
        }
    }

};

struct Prim {
    static void run(Graph &graph, std::ostream &output) {
        // Calculate edges using cities and threshold value
        graph.calculate_edges();

        // Initialize bakery chains
        vector<vector<int>> bakery_chains(graph.number_of_bakeries);
        for (int i = 0; i < graph.number_of_bakeries; i++) {
            bakery_chains[i].push_back(graph.bakery_source_indices[i]);
        }

        // Initialize assigned cities
        unordered_set<int> assigned_cities;
        unordered_map<int, unordered_set<int>> assigned_cities_to_bakery; 


        for (int i = 0; i < graph.number_of_bakeries; i++) {
            assigned_cities_to_bakery[i].insert(graph.bakery_source_indices[i]);
            assigned_cities.insert(graph.bakery_source_indices[i]);
        }

        vector<Edge> usable_edges(graph.edges);
        int assignments_this_round = 1;

        // Continue until all cities are assigned to a bakery or no more assignments are made in a round
        while (int(assigned_cities.size()) < graph.number_of_cities && assignments_this_round > 0)
        {
            assignments_this_round = 0;
            
            // Give turn to each bakery in the order they are in the array
            for (int i = 0; i < graph.number_of_bakeries; i++)
            {
                // Find the edge with highest plow that connects a city in the bakery chain and an unasigned city
                Edge edge_with_highest_plow{0, 0, 0};
                int edge_with_highest_plow_index = -1;

                for (int j = 0; j < int(usable_edges.size()); j++)
                {
                    auto& edge = usable_edges[j];

                    // Skip the edge if both source and destination are not in the bakery chain
                    if (assigned_cities_to_bakery[i].count(edge.source) == 0 && assigned_cities_to_bakery[i].count(edge.destination) == 0) 
                    {
                        continue;
                    }

                    // Skip the edge if both source and destination are in the bakery chain
                    if (assigned_cities_to_bakery[i].count(edge.source) && assigned_cities_to_bakery[i].count(edge.destination)) 
                    {
                        continue;
                    }

                    // At least one of the cities is in the current(i) bakery chain
                    // Skip the edge if the source is in the bakery chain and the destination is assigned
                    if (assigned_cities_to_bakery[i].count(edge.source) && assigned_cities.count(edge.destination)) 
                    {
                        continue;
                    }
                    // Skip the edge if the destination is in the bakery chain and the source is assigned
                    if (assigned_cities_to_bakery[i].count(edge.destination) && assigned_cities.count(edge.source)) 
                    {
                        continue;
                    }

                    // At least one of the cities is in the current(i) bakery chain and the other is not assigned
                    // Check if the edge has the highest plow
                    if (edge.weight > edge_with_highest_plow.weight)
                    {
                        edge_with_highest_plow = edge;
                        edge_with_highest_plow_index = j;
                    }
                    // If the edge has the same plow, use the city with lower index
                    else if (edge.weight == edge_with_highest_plow.weight)
                    {
                        // Find which city is not assigned for current edge
                        int city_to_add_for_current = edge.source;
                        if (assigned_cities.count(edge.source))
                            city_to_add_for_current = edge.destination;

                        // Find which city is not assigned for highest plow edge
                        int city_to_add_for_highest = edge_with_highest_plow.source;
                        if (assigned_cities.count(edge_with_highest_plow.source))
                            city_to_add_for_highest = edge_with_highest_plow.destination;
                        
                        // If the city for current edge has lower index, use it
                        if (city_to_add_for_current < city_to_add_for_highest)
                        {
                            edge_with_highest_plow = edge;
                            edge_with_highest_plow_index = j;
                        }
                    }
                }

                // If no edge was found, skip the bakery
                if (edge_with_highest_plow_index == -1)
                {
                    continue;
                }

                // Remove the edge with highest plow from the usable edges
                usable_edges.erase(usable_edges.begin() + edge_with_highest_plow_index);

                // Add the edge to the bakery chain
                int city_to_add = edge_with_highest_plow.source;
                if (assigned_cities.count(edge_with_highest_plow.source))
                {
                    city_to_add = edge_with_highest_plow.destination;
                }

                assignments_this_round++;
                // Add the city to the bakery chain
                bakery_chains[i].push_back(city_to_add);

                // Add the city to the assigned cities
                assigned_cities_to_bakery[i].insert(city_to_add);
                assigned_cities.insert(city_to_add);

                // Remove the edges that connect the 'city_to_add' to other cities that are already assigned
                // This is done to increase the performance of the algorithm
                vector<Edge> new_usable_edges;
                for (int j = 0; j < int(usable_edges.size()); j++)
                {
                    auto& edge = usable_edges[j];
                    if ((edge.source      == city_to_add && assigned_cities.count(edge.destination))
                     || (edge.destination == city_to_add && assigned_cities.count(edge.source)))
                    {
                        continue;
                    }
                    new_usable_edges.push_back(edge);
                }

                usable_edges = new_usable_edges;
            }
        }


        // City assignment to the bakeries is done
        // Output the bakery chains to the output stream
        for (int i = 0; i < graph.number_of_bakeries; i++)
        {
            output << "k" << i << " " << bakery_chains[i].size() << "\n";
            output << bakery_chains[i][0];
            for (int j = 1; j < int(bakery_chains[i].size()); j++)
            {
                output << BAKERY_ROAD_SEPARATOR << bakery_chains[i][j];
            }
            output << endl;
        }
    }
};

int main(int argc, char **argv)
{
    // Check if the user provided the input file
    if (argc != 2)
    {
        cout << "Usage: " << argv[0] << " <input.txt>" << endl;
        exit(EXIT_FAILURE);
    }

    // Open the input file
    string input_file = argv[1];
    ifstream input(input_file);

    if (!input.is_open())
    {
        cout << "Could not open file: " << input_file << endl;
        exit(EXIT_FAILURE);
    }

    Graph graph;
    // Read from the input file
    graph.read(input);

    // Close the input file
    input.close();

    ofstream output(OUTPUT_FILE);
    // Run Prim's algorithm
    Prim::run(graph, output);

    // Close the output file
    output.close();
    
    exit(EXIT_SUCCESS);
}