#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define DEBUG false

double CalcDist(int x1, int y1, int x2=0, int y2=0) {
  const int x_dist = x1-x2;
  const int y_dist = y1-y2;
  return sqrt((double) ((x_dist * x_dist) + (y_dist * y_dist)));
}

int CalcSqrDist(int x1, int y1, int x2=0, int y2=0) {
  const int x_dist = x1-x2;
  const int y_dist = y1-y2;
  return (x_dist * x_dist) + (y_dist * y_dist);
}

// Globals
// (Ugly, but best for now, especially without optimizations during compilation)
int num_cities;        // 10 <= N <= 100,000
double bcpm;           // 0.2 <= C <= 4       - Blimp Cost per Mile
double blimp_decline;  // 0.5 <= D <= 0.99    - Value reduction per 10% cities sold to.

int decline_size;      // num_cities/10
int num_declines;      //
double cur_decline;    // blimp_decline ^ num_declines
double decline_cut;    // 1.0 - blimp_decline


struct cCity {
  int x;               // -1000 < x < 1000
  int y;
  int base_price;      // Price before any decline.  P <= 100,000

  double base_dist;    // Distance from 0,0
  double onway_value;  // Value of bringing a blimp here if you were already passing through.
  double direct_value; // Value of going directly to the city and back.
  double real_value;   // Measured value at end.
  double score;        // Calculation of how valuable a city is to consider

  double angle_proxy;  // Ordered like angles, but cheaper to calculate!

  void RecalcValue() {
    onway_value =  ((double) base_price * cur_decline) - base_dist * bcpm;
    direct_value = onway_value - 2.0 * base_dist;
    // score = direct_value;
    score = onway_value;
    // score = base_price / base_dist;
  }
    
  double Dist(const cCity & city2) {
    return CalcDist(x, y, city2.x, city2.y);
  }

  void Set(int _x, int _y, int _p) {
    x =_x;  y = _y;  base_price = _p;
    base_dist = CalcDist(x,y);
    if (base_dist == 0) angle_proxy = 0.0;
    else {
      angle_proxy = ((double) x) / base_dist;      // -1.0 to 1.0
      if (y < 0) angle_proxy = 2.0 - angle_proxy;  // Come back around with 1 to 3.
    }
    RecalcValue();
//     cout << "(" << x << "," << y << ") : "
//          << base_price << " - " << base_dist * (2.0 + bcpm) << " = " << direct_value
//          << endl;
  }

  cCity() : base_price(-1){ ; }
  cCity(int _x, int _y, int _p) { Set(_x, _y, _p); }

  static bool CompareDirectValue(const cCity * city1, const cCity * city2) {
    return city1->direct_value > city2->direct_value;
  }
  static bool CompareOnwayValue(const cCity * city1, const cCity * city2) {
    return city1->onway_value > city2->onway_value;
  }
  static bool CompareScore(const cCity * city1, const cCity * city2) {
    return city1->score > city2->score;
  }
  static bool CompareAngle(const cCity * city1, const cCity * city2) {
    return city1->angle_proxy < city2->angle_proxy;
  }
  static bool CompareDistance(const cCity * city1, const cCity * city2) {
    return city1->base_dist < city2->base_dist;
  }
};

// More globals...
cCity home_city;
vector<cCity *> city_vector;   // Sorted by direct travel time.


class cTour {
private:
  vector<cCity *> city_order;
  double distance;
  double value;
  double decline_cost;
  double decline_density;

public:
  cTour() : distance(0), value(0) { ; }

  int GetSize() const { return city_order.size(); }
  int GetDistance() const { return distance; }
  int GetValue() const { return value; }
  cCity * GetCity(int id) { return city_order[id]; }

  double GetDeclineCost() const { return decline_cost; }
  double GetDeclineDensity() const { return decline_density; }

  void SwapCities(int id1, int id2) {
    cCity * tmp = city_order[id1];
    city_order[id1] = city_order[id2];
    city_order[id2] = tmp;
  }

  void SetDeclineCost(double _dc) {
    decline_cost = _dc;
    if (city_order.size() > 0) {
      decline_density = _dc / city_order.size();
    } else {
      decline_density = -1.0;
    }
  }

  void RemoveCity(int id) {
    city_order.erase(city_order.begin() + id);
  }

  bool AddCityIfValuable(cCity * city, double alt_value=0.0, double decline_level=-1) {
    if (alt_value < 0.0) alt_value = 0.0; // Never insert if less than a zero value.
    if (decline_level == -1) decline_level = cur_decline;
    const double old_value = value;

    // Put the new city into the vector.
    int cur_id = 0;
    for (cur_id = 0;
         cur_id < (int) city_order.size() && city_order[cur_id]->base_dist < city->base_dist;
         cur_id++) { ; }
    int new_pos = cur_id;
    city_order.insert(city_order.begin()+new_pos, city);

    distance = 0;
    value = 0;
    cCity * last_city = &home_city;

    for (cur_id = 0; cur_id < (int) city_order.size(); cur_id++) {      
      distance += last_city->Dist(*(city_order[cur_id]));;
      last_city = city_order[cur_id];
      value -= bcpm * distance;  // Had to take a blimp this whole way.
      value += last_city->base_price * decline_level;  // Get value for blimp.
    }

    distance += last_city->Dist(home_city); // Return trip.
    value -= distance;                      // Subtract off travel costs.

    // Now, compare this new value to its alternative and see if we keep it.
    const double val_diff = value - old_value;
    if (val_diff < alt_value) {
      city_order.erase(city_order.begin() + new_pos);
      value = old_value;
      return false;
    }
    return true;
  }

  static bool CompareDensity(const cTour * tour1, const cTour * tour2) {
    return tour1->decline_density > tour2->decline_density;
    // return tour1->decline_cost > tour2->decline_cost;
  }

  void Print() {
    if (GetSize() == 0) return;  // Ignore empty tours.
    cout << city_order[0]->x << " " << city_order[0]->y << " " << GetSize() << endl;
    for (int i = 1; i < GetSize(); i++) {
      cout << city_order[i]->x << " " << city_order[i]->y << endl;
    }
  }
};

class cTourSet {
private:
  vector<cTour *> tour_order;

public:
  int GetSize() const { return tour_order.size(); }
  cTour & GetCurTour() { return *(tour_order.back()); }
  cTour & GetPrevTour() { return *(tour_order[tour_order.size() - 2]); }
  void AddTour() { tour_order.push_back(new cTour); }

  void PrintTour(int tour_id) { tour_order[tour_id]->Print(); }

  void Reorder() {
    sort(tour_order.begin(), tour_order.end(), cTour::CompareDensity);
  }

  void PurgeEmpty() {
    for (int i = 0; i < (int) tour_order.size(); i++) {
      if (tour_order[i]->GetSize() == 0) {
        tour_order.erase(tour_order.begin()+i);
        i--;
      }
    }
  }

  // Brute-force calculate it all again to make sure we get it right.
  // Don't make changes, but do collect stats.
  double AnalyzeValue() {
    double total_value = 0.0;
    double total_distance = 0.0;
    double cur_price_factor = 1.0;
    int city_count = 0;

    double max_tour_value = 0.0;
    double min_tour_value = 1000000.0;

    cCity * prev_city = &home_city;
    for (int tour_id = 0; tour_id < (int) tour_order.size(); tour_id++) {
      cTour * cur_tour = tour_order[tour_id];
      // Start the tour from home.
      total_distance += prev_city->Dist(home_city);
      prev_city = &home_city;

      // Now take each city in order.
      double tour_distance = 0.0;
      double tour_value = 0.0;
      double tour_decline_cost = 0.0;
      for (int city_id = 0; city_id < cur_tour->GetSize(); city_id++) {
        cCity * cur_city = cur_tour->GetCity(city_id);
        double cur_dist = prev_city->Dist(*cur_city);
        tour_distance += cur_dist;

        // Analyze this city's contribution.
        cCity * next_city = &home_city;
        if (city_id+1 < cur_tour->GetSize()) next_city = cur_tour->GetCity(city_id+1);

        // Extra costs for this city are the blimp and walk to it, plus the extra
        // blimp distance to all of the subsequent cities on this tour.
        double extra_dist = cur_dist + cur_city->Dist(*next_city)
          - prev_city->Dist(*next_city);
        double extra_cost = tour_distance * bcpm; // Extra blimp whole way to here.
        extra_cost += extra_dist * (cur_tour->GetSize()-city_id-1) * bcpm; // Other blimps.
        extra_cost += extra_dist; // extra walking.
        cur_city->real_value = cur_city->base_price * cur_price_factor - extra_cost;

        // Track the effect on tour value.
        tour_value += cur_city->base_price * cur_price_factor; // Value of selling blimp
        tour_value -= tour_distance * bcpm;  // Cost of getting the blimp there.
        tour_decline_cost += cur_city->base_price * decline_cut;
        
        // Clean up
        city_count++;
        prev_city = cur_city;
        if (city_count % decline_size == 0) cur_price_factor *= blimp_decline;
      }

      // Save information about the tour.
      cur_tour->SetDeclineCost(tour_decline_cost);

      // Include this city in the tour totals.
      total_distance += tour_distance;
      total_value += tour_value;

      const double final_tour_value = tour_value - tour_distance - prev_city->Dist(home_city);
      if (max_tour_value < final_tour_value) max_tour_value = final_tour_value;
      if (min_tour_value > final_tour_value) min_tour_value = final_tour_value;
    }
    total_value -= total_distance;

    if (DEBUG) {
      cout << endl
           << "Cities: " << city_count
           << "  Tours: " << tour_order.size()
           << "  MinValue: " << min_tour_value
           << "  MaxValue: " << max_tour_value
           << endl;
    }

    return total_value;
  }

  double AnalyzeRemoval() {
    int bad_count = 0;
    double bad_total = 0.0;

    double total_value = 0.0;
    double total_distance = 0.0;
    double cur_price_factor = 1.0;
    int city_count = 0;

    double max_tour_value = 0.0;
    double min_tour_value = 1000000.0;

    cCity * prev_city = &home_city;
    for (int tour_id = 0; tour_id < (int) tour_order.size(); tour_id++) {
      cTour * cur_tour = tour_order[tour_id];
      // Start the tour from home.
      total_distance += prev_city->Dist(home_city);
      prev_city = &home_city;

      // Now take each city in order.
      double tour_distance = 0.0;
      double tour_value = 0.0;
      double tour_decline_cost = 0.0;
      for (int city_id = 0; city_id < cur_tour->GetSize(); city_id++) {
        cCity * cur_city = cur_tour->GetCity(city_id);
        double cur_dist = prev_city->Dist(*cur_city);
        tour_distance += cur_dist;

        // Analyze this city's contribution.
        cCity * next_city = &home_city;
        if (city_id+1 < cur_tour->GetSize()) next_city = cur_tour->GetCity(city_id+1);

        // Extra costs for this city are the blimp and walk to it, plus the extra
        // blimp distance to all of the subsequent cities on this tour.
        double extra_dist = cur_dist + cur_city->Dist(*next_city)
          - prev_city->Dist(*next_city);
        double extra_cost = tour_distance * bcpm; // Extra blimp whole way to here.
        extra_cost += extra_dist * (cur_tour->GetSize()-city_id-1) * bcpm; // Other blimps.
        extra_cost += extra_dist; // extra walking.
        cur_city->real_value = cur_city->base_price * cur_price_factor - extra_cost;

        // See if we need to nix this city.
        if (cur_city->real_value < 0.0) {
          // Track how bad this was.
          bad_count++;
          bad_total += cur_city->real_value;

          // Remove the city from the tour.
          cur_tour->RemoveCity(city_id);

          // Undo this city's effect on the tour.
          tour_distance -= cur_dist;
          city_id--;
        }
        else {
          // If we keep it, track the effect on tour value.
          tour_value += cur_city->base_price * cur_price_factor; // Value of selling blimp
          tour_value -= tour_distance * bcpm;  // Cost of getting the blimp there.
          tour_decline_cost += cur_city->base_price * decline_cut;

          // Clean up
          city_count++;
          prev_city = cur_city;
          if (city_count % decline_size == 0) cur_price_factor *= blimp_decline;
        }

      }

      // Save information about the tour.
      cur_tour->SetDeclineCost(tour_decline_cost);

      // Include this city in the tour totals.
      total_distance += tour_distance;
      total_value += tour_value;

      const double final_tour_value = tour_value - tour_distance - prev_city->Dist(home_city);
      if (max_tour_value < final_tour_value) max_tour_value = final_tour_value;
      if (min_tour_value > final_tour_value) min_tour_value = final_tour_value;
    }
    total_value -= total_distance;

    if (DEBUG) {
      cout << endl
           << "Cities: " << city_count
           << "  Tours: " << tour_order.size()
           << "  MinValue: " << min_tour_value
           << "  MaxValue: " << max_tour_value
           << endl
           << "  Bad Count: " << bad_count
           << "  Bad Total: " << bad_total
           << endl;
    }

    return total_value;
  }

  double AnalyzeUntangle() {
    int untangle_count = 0;
    double untangle_total = 0.0;
    
    for (int tour_id = 0; tour_id < (int) tour_order.size(); tour_id++) {
      cTour * cur_tour = tour_order[tour_id];
      if (cur_tour->GetSize() < 2) continue;
      
      // Start the tour from home.
      cCity * prev_city = &home_city;
      cCity * city1 = cur_tour->GetCity(0);
      for (int city_id = 1; city_id < cur_tour->GetSize(); city_id++) {
        cCity * city2 = cur_tour->GetCity(city_id);
        cCity * next_city = &home_city;
        if (city_id+1 < cur_tour->GetSize()) next_city = cur_tour->GetCity(city_id+1);
        
        int remain_count = cur_tour->GetSize() - city_id - 1;

        // See if we should swap city1 and city2...
        const double dist_p1 = prev_city->Dist(*city1);
        const double dist_12 = city1->Dist(*city2);
        const double dist_2n = city2->Dist(*next_city);

        const double dist_p2 = prev_city->Dist(*city2);
        const double dist_1n = city1->Dist(*next_city);

        // Benefit is the same, so we just want to minimize cost.
        // NOTE: equal factors added to both were removed. 
        double cur_cost = dist_p1 + /*dist12 +*/ dist_2n  // Distances...
          + dist_p1 * bcpm * (remain_count + 2)           // Blimp costs
          // + dist_12 * bcpm * (remain_count + 1)
          + dist_2n * bcpm * (remain_count);
        
        double alt_cost = dist_p2 + /*dist12 +*/ dist_1n  // Distances...
          + dist_p2 * bcpm * (remain_count + 2)           // Blimp costs
          // + dist_12 * bcpm * (remain_count + 1)
          + dist_1n * bcpm * (remain_count);
        
        // Should we swap 'em??
        if (alt_cost < cur_cost) {
          cur_tour->SwapCities(city_id-1, city_id);
          untangle_count++;
          untangle_total += cur_cost - alt_cost;
          prev_city = city2;
        }
        else {
          // Just juggle city ids for next iteration...
          prev_city = city1;
          city1 = city2;
        }
      }
    }

    if (DEBUG) {
      cout << endl
           << "Tours: " << tour_order.size()
           << "  Untangle Count: " << untangle_count
           << "  Untangle Total: " << untangle_total
           << endl;
    }

    return untangle_total;
  }

  void Print() {
    if (tour_order.size() == 0) return;
    PrintTour(0);
    for (int tour_id = 1; tour_id < (int) tour_order.size(); tour_id++) {
      cout << "0 0" << endl;
      PrintTour(tour_id);
    }
  }
};

void RecalcCities() {
  for (int i = 0; i < num_cities; i++) city_vector[i]->RecalcValue();
}

int main() {
  cin >> num_cities >> bcpm >> blimp_decline;
  decline_size = num_cities/10;
  num_declines = 0;
  cur_decline = 1.0;
  decline_cut = 1.0 - blimp_decline;

  // Build the home city.
  home_city.Set(0,0,0);
    
  // Load in the individual cities.
  city_vector.resize(num_cities);
  int x,y,p;
  for (int i = 0; i < num_cities; i++) {
    cin >> x >> y >> p;
    city_vector[i] = new cCity(x, y, p);
  }

  // Sort cities by score.
  sort(city_vector.begin(), city_vector.end(), cCity::CompareScore);

  const int decline_group = 2;

  // The first "decline_size" cities have the higest score.  Next, sort them by angle.
  sort(city_vector.begin(), city_vector.begin()+decline_size*decline_group, cCity::CompareAngle);

  cTourSet tour_set;
  tour_set.AddTour();
  for (int city_id = 0; city_id < num_cities; city_id++) {
    // When needed, reduce all valuations and re-sort!
    if (city_id % (decline_size*decline_group) == 0) {
      num_declines++;
      cur_decline *= blimp_decline;
      RecalcCities();

      sort(city_vector.begin()+city_id, city_vector.end(), cCity::CompareScore);
      if (city_vector[city_id]->onway_value <= 0) break;
      sort(city_vector.begin()+city_id,
           city_vector.begin()+city_id+decline_size*decline_group,
           cCity::CompareAngle);
        }

    // Three options:
    // * skip this city
    // * start a new tour with this city
    // * include this city in the current tour
    const double direct_value = city_vector[city_id]->direct_value;
    bool city_added = tour_set.GetCurTour().AddCityIfValuable(city_vector[city_id], direct_value);
    if (city_added) continue; // We're done!

    // If it wasn't added to the previous tour, see if it should have its own.
    if (direct_value > 0.0) {
      // Now build the new tour.
      tour_set.AddTour();
      tour_set.GetCurTour().AddCityIfValuable(city_vector[city_id]);
      continue;
    }

    // Otherwise we skip this city.
  }


  // We now have a solid set of tours.  Let's analyze them to see if we could
  // do better.

  while (tour_set.AnalyzeUntangle() > 1000.0);
  tour_set.AnalyzeRemoval();
  while (tour_set.AnalyzeUntangle() > 1000.0);
  
  // Re-order the tours to put the ones most affected by cuts first.
  // NOTE: Other optimizations that assume angles become impossible after this.
  tour_set.Reorder();

  // Print out the results.
  tour_set.PurgeEmpty();
  tour_set.Print();
  if (DEBUG) cout << endl << "Total value = " << tour_set.AnalyzeValue() << endl;
  if (DEBUG) cout << endl << "Untangle Potential = " << tour_set.AnalyzeUntangle() << endl;

  return 0;
}


// @CAO
// Try putting skipped cities back in later.
// Hold off on starting a new tour until TWO (more?) cities don't make sense.
// Try moving cities to neighboring tours -- especially those with the largest current costs
// Use different techniques for smaller worlds.
// If an added value is low, perhaps remove it to make room for something with a higher value

// Make sure we calculate added value correctly.
// Try some alternate scoring methods.

// --speeedups--
// Have tours contain a linked list of cities, not an array.
// Cache the Dist() calculation in cities.