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:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author cacophonix
 */
public class Main {
    public static void main(String[] args) {
        new Thread(null,new TaskE(),"",1<<28).start();
    }

    static class TaskE implements Runnable {

        public void run(){
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            InputReader in = new InputReader(inputStream);
            OutputWriter out = new OutputWriter(outputStream);

            solve(1, in, out);
            out.close();
        }

        int n;
        int m;
        int x;
        int y;
        int[] from;
        int[] to;
        int[] mashrooms;
        long ans;
        int[] color;
        ArrayList<IntIntPair>[] eds;
        ArrayList<IntIntPair> edges;
        long[] visited;
        long[] sum_by_color;

        long fun(long w) {
            long lo = 0;
            long hi = 100000002;
            long mid;
            while (lo < hi) {
                mid = (lo + hi) >> 1;
                if (mid * mid + mid >= 2 * w) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }
            return hi * w - hi * (hi - 1) * (hi + 1) / 6;

        }

        long fun_max(int node) {


            if (visited[node] != -1) {
                return visited[node];
            }

            long ret = 0;
            ret = sum_by_color[node];

            for (int i = 0; i < eds[node].size(); i++) {
                int to = eds[node].get(i).first;
                int edge = eds[node].get(i).second;
                long val = mashrooms[edge];
                ret = Math.max(ret, sum_by_color[node] + val + fun_max(to));
            }

            visited[node] = ret;
            return ret;
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.readInt();
            m = in.readInt();


            sum_by_color = new long[n + 1];
            visited = new long[n];
            Arrays.fill(visited, -1);
            edges = new ArrayList<>();
            mashrooms = new int[m];
            from = new int[m];
            to = new int[m];
            eds = new ArrayList[n];

            for (int i = 0; i < n; i++) {
                eds[i] = new ArrayList<>();
            }

            Graph graph = new Graph(n, m);
            for (int i = 0; i < m; i++) {
                x = in.readInt();
                x--;
                y = in.readInt();
                y--;
                from[i] = x;
                to[i] = y;
                mashrooms[i] = in.readInt();
                graph.addSimpleEdge(x, y);
            }
            int[] tem = new int[1];

            //color = StronglyConnectedComponents.kosaraju(graph).first;

            color = StronglyConnectedComponents.tarjan(graph);

//        if(n==85) {
//            out.printLine(tem);
//            out.printLine(color);
//            for(int i=0;i<n;i++){
//                if(tem[i]!=color[i]){
//                    out.printLine("hic");
//                }
//            }
//        }

            ans = 0;
            for (int i = 0; i < m; i++) {
                if (color[from[i]] == color[to[i]]) {
                    sum_by_color[color[from[i]]] += fun(mashrooms[i]);
                }
            }


            for (int i = 0; i < m; i++) {
                edges.add(IntIntPair.makePair(-mashrooms[i], i));
            }

            Collections.sort(edges);


            for (int i = 0; i < m; i++) {

                int ii = edges.get(i).second;

                x = color[from[ii]];
                y = color[to[ii]];
                if (x == y) continue;

                eds[x].add(IntIntPair.makePair(y, ii));


            }
            x = in.readInt();
            x--;
            ans += fun_max(color[x]);

            out.printLine(ans);

        }

    }

    static class StronglyConnectedComponents {
        private final Graph graph;
        private int[] order;
        private int[] lowlink;
        private int[] stack;
        private int stack_pos;
        private int color;
        private boolean[] visited;
        private int index = 0;
        private int vertexCount;
        private int[] condensed;

        private StronglyConnectedComponents(Graph graph) {
            this.graph = graph;
            vertexCount = graph.vertexCount();
            order = new int[vertexCount];
            visited = new boolean[vertexCount];
            condensed = new int[vertexCount];
        }

        public static int[] tarjan(Graph graph) {
            return new StronglyConnectedComponents(graph).tarjan();
        }

        private int[] tarjan() {
            lowlink = new int[vertexCount];
            stack = new int[vertexCount];
            index = 1;
            for (int i = 0; i < vertexCount; i++) {
                if (order[i] == 0) {
                    calculate_tarjan(i);
                }
            }
            return condensed;
        }

        private void calculate_tarjan(int node) {
            visited[node] = true;
            stack[stack_pos++] = node;
            lowlink[node] = index;
            order[node] = index;
            index++;
            int edge = graph.firstOutbound(node);
            while (edge != -1) {
                int next = graph.destination(edge);
                if (visited[next]) {
                    lowlink[node] = Math.min(lowlink[node], order[next]);
                } else if (order[next] == 0) {
                    calculate_tarjan(next);
                    lowlink[node] = Math.min(lowlink[node], lowlink[next]);
                }
                edge = graph.nextOutbound(edge);
            }
            if (lowlink[node] == order[node]) {
                int current;
                do {
                    current = stack[stack_pos - 1];
                    stack_pos--;
                    condensed[current] = color;
                    visited[current] = false;
                } while (current != node);
                color++;
            }
        }

    }

    static interface Edge {
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(long i) {
            writer.println(i);
        }

    }

    static class IntIntPair implements Comparable<IntIntPair> {
        public final int first;
        public final int second;

        public static IntIntPair makePair(int first, int second) {
            return new IntIntPair(first, second);
        }

        public IntIntPair(int first, int second) {
            this.first = first;
            this.second = second;
        }


        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            IntIntPair pair = (IntIntPair) o;

            return first == pair.first && second == pair.second;
        }


        public int hashCode() {
            int result = first;
            result = 31 * result + second;
            return result;
        }


        public String toString() {
            return "(" + first + "," + second + ")";
        }

        @SuppressWarnings({"unchecked"})
        public int compareTo(IntIntPair o) {
            int value = Integer.compare(first, o.first);
            if (value != 0) {
                return value;
            }
            return Integer.compare(second, o.second);
        }

    }

    static class Graph {
        public static final int REMOVED_BIT = 0;
        protected int vertexCount;
        protected int edgeCount;
        private int[] firstOutbound;
        private int[] firstInbound;
        private Edge[] edges;
        private int[] nextInbound;
        private int[] nextOutbound;
        private int[] from;
        private int[] to;
        private long[] weight;
        public long[] capacity;
        private int[] reverseEdge;
        private int[] flags;

        public Graph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public Graph(int vertexCount, int edgeCapacity) {
            this.vertexCount = vertexCount;
            firstOutbound = new int[vertexCount];
            Arrays.fill(firstOutbound, -1);

            from = new int[edgeCapacity];
            to = new int[edgeCapacity];
            nextOutbound = new int[edgeCapacity];
            flags = new int[edgeCapacity];
        }

        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            ensureEdgeCapacity(edgeCount + 1);
            if (firstOutbound[fromID] != -1) {
                nextOutbound[edgeCount] = firstOutbound[fromID];
            } else {
                nextOutbound[edgeCount] = -1;
            }
            firstOutbound[fromID] = edgeCount;
            if (firstInbound != null) {
                if (firstInbound[toID] != -1) {
                    nextInbound[edgeCount] = firstInbound[toID];
                } else {
                    nextInbound[edgeCount] = -1;
                }
                firstInbound[toID] = edgeCount;
            }
            this.from[edgeCount] = fromID;
            this.to[edgeCount] = toID;
            if (capacity != 0) {
                if (this.capacity == null) {
                    this.capacity = new long[from.length];
                }
                this.capacity[edgeCount] = capacity;
            }
            if (weight != 0) {
                if (this.weight == null) {
                    this.weight = new long[from.length];
                }
                this.weight[edgeCount] = weight;
            }
            if (reverseEdge != -1) {
                if (this.reverseEdge == null) {
                    this.reverseEdge = new int[from.length];
                    Arrays.fill(this.reverseEdge, 0, edgeCount, -1);
                }
                this.reverseEdge[edgeCount] = reverseEdge;
            }
            if (edges != null) {
                edges[edgeCount] = createEdge(edgeCount);
            }
            return edgeCount++;
        }

        protected final GraphEdge createEdge(int id) {
            return new GraphEdge(id);
        }

        public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) {
            if (capacity == 0) {
                return addEdge(from, to, weight, 0, -1);
            } else {
                int lastEdgeCount = edgeCount;
                addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge());
                return addEdge(from, to, weight, capacity, lastEdgeCount);
            }
        }

        protected int entriesPerEdge() {
            return 1;
        }

        public final int addWeightedEdge(int from, int to, long weight) {
            return addFlowWeightedEdge(from, to, weight, 0);
        }

        public final int addSimpleEdge(int from, int to) {
            return addWeightedEdge(from, to, 0);
        }

        public final int vertexCount() {
            return vertexCount;
        }

        public final int firstOutbound(int vertex) {
            int id = firstOutbound[vertex];
            while (id != -1 && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int nextOutbound(int id) {
            id = nextOutbound[id];
            while (id != -1 && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int destination(int id) {
            return to[id];
        }

        public final boolean flag(int id, int bit) {
            return (flags[id] >> bit & 1) != 0;
        }

        public final boolean isRemoved(int id) {
            return flag(id, REMOVED_BIT);
        }

        protected void ensureEdgeCapacity(int size) {
            if (from.length < size) {
                int newSize = Math.max(size, 2 * from.length);
                if (edges != null) {
                    edges = resize(edges, newSize);
                }
                from = resize(from, newSize);
                to = resize(to, newSize);
                nextOutbound = resize(nextOutbound, newSize);
                if (nextInbound != null) {
                    nextInbound = resize(nextInbound, newSize);
                }
                if (weight != null) {
                    weight = resize(weight, newSize);
                }
                if (capacity != null) {
                    capacity = resize(capacity, newSize);
                }
                if (reverseEdge != null) {
                    reverseEdge = resize(reverseEdge, newSize);
                }
                flags = resize(flags, newSize);
            }
        }

        protected final int[] resize(int[] array, int size) {
            int[] newArray = new int[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private long[] resize(long[] array, int size) {
            long[] newArray = new long[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private Edge[] resize(Edge[] array, int size) {
            Edge[] newArray = new Edge[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        protected class GraphEdge implements Edge {
            protected int id;

            protected GraphEdge(int id) {
                this.id = id;
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}