Problem: Ralph is going to collect mushrooms in the Mushroom Forest. 

There are m directed paths connecting n trees in the Mushroom Forest. On each path grow some mushrooms. When Ralph passes a path, he collects all the mushrooms on the path. The Mushroom Forest has a magical fertile ground where mushrooms grow at a fantastic speed. New mushrooms regrow as soon as Ralph finishes mushroom collection on a path. More specifically, after Ralph passes a path the i-th time, there regrow i mushrooms less than there was before this pass. That is, if there is initially x mushrooms on a path, then Ralph will collect x mushrooms for the first time, x - 1 mushrooms the second time, x - 1 - 2 mushrooms the third time, and so on. However, the number of mushrooms can never be less than 0.

For example, let there be 9 mushrooms on a path initially. The number of mushrooms that can be collected from the path is 9, 8, 6 and 3 when Ralph passes by from first to fourth time. From the fifth time and later Ralph can't collect any mushrooms from the path (but still can pass it).

Ralph decided to start from the tree s. How many mushrooms can he collect using only described paths?

Input

The first line contains two integers n and m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106), representing the number of trees and the number of directed paths in the Mushroom Forest, respectively.

Each of the following m lines contains three integers x, y and w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108), denoting a path that leads from tree x to tree y with w mushrooms initially. There can be paths that lead from a tree to itself, and multiple paths between the same pair of trees.

The last line contains a single integer s (1 ≤ s ≤ n) — the starting position of Ralph. 

Output

Print an integer denoting the maximum number of the mushrooms Ralph can collect during his route. 

Examples

Input

2 2
1 2 4
2 1 4
1


Output

16

Input

3 3
1 2 4
2 3 3
1 3 8
1


Output

8

Note

In the first sample Ralph can pass three times on the circle and collect 4 + 4 + 3 + 3 + 1 + 1 = 16 mushrooms. After that there will be no mushrooms for Ralph to collect.

In the second sample, Ralph can go to tree 3 and collect 8 mushrooms on the path from tree 1 to tree 3.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int ni() {
  int val;
  scanf("%i", &val);
  return val;
}
pair<int, int> npi() {
  pair<int, int> val;
  scanf("%i %i", &val.first, &val.second);
  return val;
}
int64_t nll() {
  int64_t val;
  scanf("%I64d", &val);
  return val;
}
vector<int> nvi(int n, int corr = 0) {
  vector<int> a(n);
  for (int i = 0; i < n; ++i) a[i] = ni() + corr;
  return move(a);
}
char nc() {
  char val;
  do {
    val = getchar();
  } while (val == ' ' || val == '\r' || val == '\n');
  return val;
}
char ncs() {
  char val;
  do {
    val = getchar();
  } while (false);
  return val;
}
string ns() {
  static char buff[1024 * 4000];
  scanf("%s", buff);
  return string{buff};
}
int64_t gcd(int64_t a, int64_t b) {
  while (b) {
    auto tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}
int64_t tr2(int xv1, int yv1, int xv2, int yv2, int x3, int y3) {
  return 1LL * (xv2 - xv1) * (y3 - yv1) - 1LL * (yv2 - yv1) * (x3 - xv1);
}
const long double eps = 1e-12;
const long double pi = acos(-1.0);
bool eq(long double a, long double b) { return abs(a - b) <= eps; }
int8_t bits_cnt[256];
const string input_dir = "inputs\\";
string input_file = input_dir + "input.txt";
string output_file = input_dir + "output.txt";
void init_streams() {}
void init_data() {
  for (int i = 1; i <= 255; ++i)
    for (int j = 0; j < 8; ++j)
      if ((1 << j) & i) ++bits_cnt[i];
}
int get_bit_count(int v) {
  return bits_cnt[v & 0xFF] + bits_cnt[(v >> 8) & 0xFF] +
         bits_cnt[(v >> 16) & 0xFF] + bits_cnt[(v >> 24) & 0xFF];
}
struct Edge {
  int to;
  int w;
  int nxt;
};
const int maxn = 1000 * 1000 + 1;
const int maxm = 1000 * 1000 + 1;
int last[2][maxn], first[2][maxn];
long long block_sum[15000];
vector<int> wval;
int stored = 0;
Edge g[2][maxm];
int cstored = 0;
Edge cg[maxm];
int clast[maxn], cfirst[maxn];
void precalc_blocks() {
  const int maxw = 100000000 + 1;
  int block_id = 1, offset = 1, sz = 1;
  block_sum[1] = 1;
  long long sm = block_sum[1];
  wval.push_back(1);
  while (offset + sz <= maxw) {
    offset += sz;
    sm = sm + sz * sz + 1;
    block_sum[++sz] = sm;
    wval.push_back(offset);
  }
}
long long get_sum(int w) {
  if (w == 1) return 1;
  if (w == 2) return 3;
  auto it = lower_bound((wval).begin(), (wval).end(), w);
  if (it == wval.end() || *it > w) --it;
  long long id = it - wval.begin() + 1;
  auto disp = w - *it;
  return block_sum[id] + id * disp;
}
void add_edge(int from, int to, int w) {
  g[0][stored] = Edge{to, w, -1};
  if (first[0][from] < 0) {
    first[0][from] = stored;
    last[0][from] = stored;
  } else {
    g[0][last[0][from]].nxt = stored;
    last[0][from] = stored;
  }
  g[1][stored] = Edge{from, w, -1};
  if (first[1][to] < 0) {
    first[1][to] = stored;
    last[1][to] = stored;
  } else {
    g[1][last[1][to]].nxt = stored;
    last[1][to] = stored;
  }
  ++stored;
}
void add_cedge(int from, int to, int w) {
  cg[cstored] = Edge{to, w, -1};
  if (cfirst[from] < 0) {
    cfirst[from] = cstored;
    clast[from] = cstored;
  } else {
    cg[clast[from]].nxt = cstored;
    clast[from] = cstored;
  }
  ++cstored;
}
vector<int> order, comp;
vector<int8_t> used, used1;
vector<int> remap;
vector<long long> comp_w;
vector<long long> dp;
int nn;
void dfs1(int v) {
  used1[v] = 1;
  for (auto id = first[0][v]; id >= 0; id = g[0][id].nxt)
    if (!used1[g[0][id].to]) dfs1(g[0][id].to);
  order.emplace_back(v);
}
void dfs2(int v) {
  used[v] = 1;
  comp.emplace_back(v);
  for (auto id = first[1][v]; id >= 0; id = g[1][id].nxt)
    if (!used[g[1][id].to] && used1[g[1][id].to]) dfs2(g[1][id].to);
}
long long dfs3(int v) {
  if (dp[v] < 0) {
    long long ans = 0;
    for (auto id = cfirst[v]; id >= 0; id = cg[id].nxt)
      ans = max(ans, cg[id].w + dfs3(cg[id].to));
    dp[v] = ans + comp_w[v];
  }
  return dp[v];
}
vector<int> get_comp_edges(const vector<int>& comp) {
  vector<int> res;
  for (auto v : comp) {
    for (auto id = first[1][v]; id >= 0; id = g[1][id].nxt) {
      if (binary_search((comp).begin(), (comp).end(), g[1][id].to))
        res.push_back(id);
    }
  }
  return move(res);
}
int main() {
  init_streams();
  init_data();
  for (int j = 0; j < 2; ++j)
    for (int i = 0; i < maxn; ++i) {
      first[j][i] = last[j][i] = -1;
      if (j == 0) cfirst[i] = clast[i] = -1;
    }
  precalc_blocks();
  auto n = ni(), m = ni();
  for (int i = 0; i < m; ++i) {
    int x, y, w;
    scanf("%i %i %i", &x, &y, &w);
    add_edge(x, y, w);
  }
  auto s = ni();
  used1.assign(n + 1, 0);
  dfs1(s);
  auto sz = order.size();
  used.assign(n + 1, 0);
  remap.assign(n + 1, -1);
  comp_w.assign(n + 1, 0);
  for (int i = 0, comp_id = 0; i < sz; ++i) {
    auto v = order[sz - 1 - i];
    if (!used[v]) {
      comp.clear();
      dfs2(v);
      for (auto u : comp) remap[u] = comp_id;
      sort((comp).begin(), (comp).end());
      auto edgelist = get_comp_edges(comp);
      for (auto edge_id : edgelist) comp_w[comp_id] += get_sum(g[1][edge_id].w);
      ++comp_id;
      nn = comp_id;
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (auto id = first[0][i]; id >= 0; id = g[0][id].nxt) {
      auto u = remap[i], v = remap[g[0][id].to];
      if (u >= 0 && v >= 0 && u != v) add_cedge(u, v, g[0][id].w);
    }
  }
  dp.assign(n + 1, -1);
  auto ans = dfs3(remap[s]);
  cout << ans << endl;
  return 0;
}