Example

Input

2 10
Warsaw Petersburg
3
Kiev Moscow Petersburg
150 120
3
Moscow Minsk Warsaw
100 150


Output

380 1
#include <bits/stdc++.h>
using namespace std;
struct edge {
  int t, cost;
  edge() {}
  edge(int tt, int cc) {
    t = tt;
    cost = cc;
  }
};
struct eel {
  int v, cost, tra;
  eel() {}
  eel(int vv, int cc, int tt) {
    v = vv;
    cost = cc;
    tra = tt;
  }
  bool operator<(const eel &e) const {
    if (cost == e.cost) return tra > e.tra;
    return cost > e.cost;
  }
};
int n, t;
int all;
int id[100001];
bool transfer[100001];
pair<int, int> dist[100001];
vector<int> same[100001];
vector<edge> G[100001];
map<string, int> data;
pair<int, int> dijk(int start, int goal) {
  priority_queue<eel> que;
  memset(transfer, false, sizeof(transfer));
  for (int i = 0; i < all; i++) {
    dist[i].first = 2000000005;
    dist[i].second = 2000000005;
  }
  for (int i = 0; i < same[start].size(); i++) {
    que.push(eel(same[start][i], 0, 0));
    dist[same[start][i]] = pair<int, int>(0, 0);
  }
  transfer[start] = true;
  while (que.size()) {
    eel q = que.top();
    que.pop();
    if (dist[q.v].first < q.cost || dist[q.v].second < q.tra) continue;
    printf("%d %d %d\n", q.v, q.cost, q.tra);
    if (id[q.v] == goal) return pair<int, int>(q.cost, q.tra);
    for (int i = 0; i < G[q.v].size(); i++) {
      edge e = G[q.v][i];
      if (dist[e.t].first > q.cost + e.cost ||
          (dist[e.t].first == q.cost + e.cost && dist[e.t].second > q.tra)) {
        dist[e.t] = pair<int, int>(q.cost + e.cost, q.tra);
        que.push(eel(e.t, q.cost + e.cost, q.tra));
      }
    }
    if (!transfer[id[q.v]]) {
      transfer[id[q.v]] = true;
      for (int i = 0; i < same[id[q.v]].size(); i++) {
        int next = same[id[q.v]][i];
        if (next == q.v) continue;
        dist[next] = pair<int, int>(q.cost + t, q.tra + 1);
        que.push(eel(next, q.cost + t, q.tra + 1));
      }
    }
  }
  return pair<int, int>(-1, -1);
}
int main(void) {
  scanf("%d%d%*c", &n, &t);
  printf("%d %d\n", n, t);
  string str;
  string A;
  string B;
  getline(cin, str);
  istringstream stream(str);
  getline(stream, A, ' ');
  getline(stream, B);
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%d%*c", &a);
    int prev = all;
    getline(cin, str);
    istringstream stream(str);
    string name;
    while (getline(stream, name, ' ')) {
      if (data.find(name) == data.end()) {
        int next = data.size();
        data[name] = next;
      }
      id[all] = data[name];
      same[data[name]].push_back(all);
      all++;
    }
    for (int j = 0; j < a - 1; j++) {
      int tt;
      scanf("%d%*c", &tt);
      G[prev + j].push_back(edge(prev + j + 1, tt));
      G[prev + j + 1].push_back(edge(prev + j, tt));
    }
  }
  pair<int, int> res = dijk(data[A], data[B]);
  if (res.first == -1)
    printf("-1\n");
  else
    printf("%d %d\n", res.first, res.second);
  return 0;
}
