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 JAVA):

Solution:
/**
 * Created by Aminul on 9/23/2019.
 */

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Stack;

import static java.lang.Math.cos;
import static java.lang.Math.max;

public class CF_894E_3 {
    static int[][][] dag;
    static long dp[];
    static boolean vis[];
    static int from[] = new int[(int) 1e6], to[] = new int[(int) 1e6], cost[] = new int[(int) 1e6];
    static int[] p = new int[(int)1e6];

    public static void main(String[] args) throws Exception {
        new Thread(null, new Runnable() {
            public void run() {
                try {
                    solveIt();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }, "Main", 1 << 28).start();
    }

    public static void solveIt() throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt(), m = in.nextInt();
        int edges[][] = new int[m][];

        for (int i = 0; i < m; i++) {
            int u = in.nextInt(), v = in.nextInt(), w = in.nextInt();
            u--;
            v--;
            from[i] = u;
            to[i] = v;
            edges[i] = new int[]{u, v, w};
        }
        int g[][] = packD(n, from, to);
        int src = in.nextInt() - 1;
        pw.println(solve(src, n, m, g, edges));
        pw.close();
    }

    static long solve(int src, int n, int m, int g[][], int edges[][]) {
        SCCTarjan scc = new SCCTarjan();
        int clr[] = scc.scc(g);
        int c = 0;
        for (int i = 0; i < n; i++) {
            c = max(c, clr[i] + 1);
        }
        dp = new long[c];
        int idx = 0;
        for (int e[] : edges) {
            int u = e[0], v = e[1];
            long w = calcCost(e[2]);
            if (clr[u] == clr[v]) dp[clr[u]] += w;
            else {
                from[idx] = clr[u];
                to[idx] = clr[v];
                cost[idx] = e[2];
                idx++;
            }
        }
        dag = packWD(c, from, to, cost, idx);
        vis = new boolean[c];
        dfs(clr[src]);
        return dp[clr[src]];
    }

    static void dfs(int u) {
        if (vis[u]) return;
        vis[u] = true;
        long max = 0;
        for (int e[] : dag[u]) {
            if (!vis[e[0]]) dfs(e[0]);
            max = max(max, e[1] + dp[e[0]]);
        }
        dp[u] += max;
    }

    static long calcCost(long w) {
        long n = binarySearch(w);
        long res = (n + 1) * w;
        res -= ((n * (n + 1) / 2) * (n + 2)) / 3; // 1 + 3 + 6 + 10 ... = (n * (n + 1) * (n + 2)) / 6
        return res;
    }

    static long binarySearch(long k) {
        long lo = 0, hi = k + 1, mid;
        while (lo < hi) {
            mid = (lo + hi) / 2;
            long s = (mid * (mid + 1)) / 2;
            if (s > k) hi = mid;
            else lo = mid + 1;
        }
        if ((lo * (lo + 1)) / 2 > k) lo--;
        return lo; //returns the lowest index where arr[lo] >= key;
    }

    static long calcCost_2(int x) {
        int lb = 0, rb = 1 << 30;
        while (lb < rb) {
            int md = (lb + rb + 1) >> 1;
            if (1l * md * (md + 1) / 2 < x)
                lb = md;
            else
                rb = md - 1;
        }
        int y = lb;
        return 1l * (y + 1) * x - 1l * y * (y + 1) * (y + 2) / 6;
    }

    public static int[][] packD(int n, int[] from, int[] to) {
        return packD(n, from, to, from.length);
    }

    public static int[][] packD(int n, int[] from, int[] to, int sup) {
        int[][] g = new int[n][];
        for (int i = 0; i < sup; i++) p[from[i]]++;
        for (int i = 0; i < n; i++) g[i] = new int[p[i]];
        for (int i = 0; i < sup; i++) {
            g[from[i]][--p[from[i]]] = to[i];
        }
        return g;
    }

    public static int[][][] packWD(int n, int[] from, int[] to, int[] w, int sup) {
        int[][][] g = new int[n][][];
        for (int i = 0; i < sup; i++) p[from[i]]++;
        for (int i = 0; i < n; i++)
            g[i] = new int[p[i]][2];
        for (int i = 0; i < sup; i++) {
            --p[from[i]];
            g[from[i]][p[from[i]]][0] = to[i];
            g[from[i]][p[from[i]]][1] = w[i];
        }
        return g;
    }

    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }


    static class SCCTarjan {
        int[][] graph;
        boolean[] visited;
        Stack<Integer> stack;
        int time, cmp, lowlink[], component[];

        public int[] scc(int[][] graph) { //0-based nodes
            int n = graph.length;
            this.graph = graph;
            visited = new boolean[n];
            stack = new Stack<>();
            time = 0;
            lowlink = new int[n];
            component = new int[n];

            for (int u = 0; u < n; u++)
                if (!visited[u])
                    dfs(u);

            return component;
        }

        void dfs(int u) {
            lowlink[u] = time++;
            visited[u] = true;
            stack.add(u);
            boolean isComponentRoot = true;

            for (int v : graph[u]) {
                if (!visited[v])
                    dfs(v);
                if (lowlink[u] > lowlink[v]) {
                    lowlink[u] = lowlink[v];
                    isComponentRoot = false;
                }
            }

            if (isComponentRoot) {
                while (true) {
                    int x = stack.pop();
                    component[x] = cmp;
                    lowlink[x] = Integer.MAX_VALUE;
                    if (x == u)
                        break;
                }
                ++cmp;
            }
        }
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;

        public FastReader(InputStream is) {
            this.is = is;
        }

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }


        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)) {
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public char readChar() {
            return (char) skip();
        }
    }
}