#include <bits/stdc++.h>
#define int long long
#define __int32 signed
#define log ropeorp

using namespace std;

const int NMAX = 130;
const int INF = 1e18;
const int LIM = 10;
const int MOD = 1e9 + 7;

int n, m, k, s;
int log[NMAX];
int deg[NMAX];

struct rectangle {
      int x1, y1; // левый верхний
      int x2, y2; // правый нижний
} a[NMAX][NMAX];

rectangle dp[NMAX][NMAX][LIM][LIM];

inline void pre_calc_deg(void) {
      deg[0] = 1;
      for (int i = 1; i < NMAX; ++i) deg[i] = (deg[i - 1] * 2) % MOD;
}

inline void pre_calc_log(void) {
      log[0] = log[1] = 0;
      for (int i = 2; i < NMAX; ++i) log[i] = log[i / 2] + 1;
}


rectangle overall_cut(rectangle a, rectangle b) {
      // (ax1, ay1) (ax2, ay2) - прямоугольник A
      // (bx1, by1) (bx2, by2) - прямоугольник B

      int ax1 = a.x1;
      int ay1 = a.y1;
      int ax2 = a.x2;
      int ay2 = a.y2;

      int bx1 = b.x1;
      int by1 = b.y1;
      int bx2 = b.x2;
      int by2 = b.y2;


      if ((ax1 == -INF) or (bx1 == -INF))  return rectangle{-INF,-INF,-INF,-INF};

      if (ay2>by1 || ay1<by2 || ax1 > bx2 || ax2 <bx1) {
            return rectangle{-INF,-INF,-INF,-INF};
      }
      else {
            int cy1, cy2, cx1, cx2;
            cy1 = min(ay1, by1);
            cx1 = max(ax1, bx1);
            cy2 = max(ay2, by2);
            cx2 = min(ax2, bx2);
            return rectangle{cx1, cy1, cx2, cy2};
      }

}

int sq(rectangle a) {
      return (abs(a.x1 - a.x2) * abs(a.y1 - a.y2));
}

__int32 main() {

      //precalc
      pre_calc_deg();
      pre_calc_log();

      int n, m;
      cin >> n >> m;

      for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                  rectangle temp;
                  cin >> temp.x1 >> temp.y1 >> temp.x2 >> temp.y2;
                  // привести к нормальному виду
                  if (temp.x1 > temp.x2) swap(temp.x1, temp.x2);
                  if (temp.y1 < temp.y2) swap(temp.y1, temp.y2);
                  a[i][j] = temp;
            }
      }

      for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                  for (int k1 = 0; k1 < LIM; ++k1) {
                        for (int k2 = 0; k2 < LIM; ++k2) {
                              if ((k1 == 0) and (k2 == 0)) {
                                    dp[i][j][k1][k2] = a[i][j];
                              }
                        }
                  }
            }
      }

      for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                  for (int lg = 0; lg < LIM; ++lg) {
                        dp[i][j][0][lg] = overall_cut(dp[i][j][0][lg - 1], dp[i][j + deg[lg - 1]][0][lg - 1]);
                  }
            }
      }

      for (int k1 = 1; k1 < LIM; ++k1) {
            for (int i = 0; i < n; ++i) {
                  for (int k2 = 1; k2 < LIM; ++k2) {
                        for (int j = 0; j < m; ++j) {
                              dp[i][j][k1][k1] = overall_cut(dp[i][j][k1 - 1][k2], dp[i + deg[k1 - 1]][j][k1 - 1][k2]);
                        }
                  }
            }
      }

      int reu(int i) {
            if (i > n) return (i - n);
            else return (i);
      }

      pair <double, vector<int>> dij(double x) {
            vector <double> d(2 * n + 1, INF); d[x] = 0;
            vector <int>  way(2 * n + 1, -1);
            set <pair<double, int>> que;
            que.insert(make_pair(0, x));
            while (que.size()) {
                  auto top = *que.begin();
                  int from = top.second;
                  int len = top.first;
                  que.erase(top);
                  if (d[from] != top.first) continue;

                  for (auto v : graph[from]) {
                        if (d[v.first] > d[from] + v.second) {
                              d[v.first] = d[from] + v.second;
                              way[v.first] = from;
                              que.insert(make_pair(d[v.first], v.first));
                        }
                  }
            }

            vector <int> result;

            for (int i = n + 1; i != 1; i = way[i]) {
                  if (i == -1) break;
                  if (result.size() == 0 || reu(i) != reu(result.back())) result.push_back(reu(i));
                  if (i == -1) break;
            }

            return make_pair(d[n + 1], result);
      }
      cin >> n;

      vector <pair<double, double>> v; // first - ���������, second - ��������
      v.push_back(make_pair(INF, INF));

      for (int i = 1; i <= n; ++i) {
            int a, b;
            cin >> a >> b;
            v.push_back(make_pair(a, b));
      }

      for (int i = 0; i < n - 1; ++i) {
            double a, b, len;
            cin >> a >> b >> len;
            g[(int)a].push_back(make_pair(b, len));
            g[(int)b].push_back(make_pair(a, len));
      }

      for (int i = 1; i <= n; ++i) {
            start = i;
            dfs(i, 0);
      }

      for (int i = 2; i <= n; ++i) {
            graph[i].push_back(make_pair(n + i, v[i].first));
      }


      for (int i = 1; i <= n; ++i) {
            for (int j = n + 1; j <= 2 * n; ++j) {
                  if (j != n + i) {
                        graph[j].push_back(make_pair(i, len[i][j - n] / v[i].second));
                  }
            }
      }

      double ans = -INF;
      vector <int> out;

      double len[N];
      fill(len, len + N, INF);
      len[n + 1] = 0;
      len[1] = 0;


      vector <char> vis(n * 2 + 1, false);
      vector <int> p(n * 2 + 1, -1);

      for (int i = 1; i <= 2 * n; ++i) {
            int v = -1;

            for (int j = 1; j <= 2 * n; ++j) {
                  if (!vis[j] && (v == -1 || len[j] < len[v])) v = j;
            }

            vis[v] = 1;

            for (auto t : graph[v]) {
                  int to = t.first;
                  double d = t.second;
                  if (len[v] + d < len[to]) {
                        len[to] = len[v] + d;
                        p[to] = v;
                  }
            }

      }

      int reg = -1;

      for (int i = n + 1; i <= 2 * n; ++i) {
            if (len[i] > ans) {
                  ans = len[i];
                  reg = i;
            }
      }

      vector <int> way;

      for (int i = reg; i != -1; i = p[i]) {
            way.push_back(i);
      }

      cout << fixed << setprecision(10) << ans << '\n';

      for (auto i : way) {
            if (i <= n) {
                  cout << i << ' ';
            }
      }
      cout << 1 << '\n';

      return 0;
}