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.*;
import java.util.*;


public class A implements Runnable{

	static ArrayList<pair>[] adjList;
	static int V, counter, SCC, dfs_num[], dfs_low[], comp[];
	static boolean[] inSCC, vis;
	// static Stack<Integer> stack;
	static long memo[];
	static int SP;
	static int[] stack;

	static void tarjanSCC() // O(V + E)
	{
		dfs_low = new int[V];
		dfs_num = new int[V];
		stack = new int[V];
		inSCC = new boolean[V];
		for (int i = 0; i < V; ++i)
			if (dfs_num[i] == 0)
				tarjanSCC(i);
	}

	static void tarjanSCC(int u) {
		dfs_num[u] = dfs_low[u] = ++counter;
		stack[SP++] = u;

		for (pair v : adjList[u]) {
			if (dfs_num[v.x] == 0)
				tarjanSCC(v.x);
			if (!inSCC[v.x])
				dfs_low[u] = Math.min(dfs_low[u], dfs_low[v.x]);
		}
		if (dfs_num[u] == dfs_low[u]) {
			// SCC found
			SCC++;
			while (true) {
				int v = stack[--SP];
				comp[v] = SCC - 1;
				inSCC[v] = true;
				if (v == u)
					break;
			}
		}
	}

	static long[] cost, get, prefixsum;

	static long get(int x) {
		int lo = 0;
		int hi = get.length - 1;
		int ans = 0;
		while (lo <= hi) {
			int mid = lo + hi >> 1;
			if (get[mid] <= x) {
				ans = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}

		}
		long sum = (ans + 1) * 1l * x - prefixsum[ans];
		return sum;
	}

	static long dfs(int u) {
		long max = 0;
		for (pair v : g[u]) {
			if (memo[v.x] != -1)
				max = Math.max(max, memo[v.x] + v.y);
			else
				max = Math.max(max, dfs(v.x) + v.y);
		}
		return memo[u] = (max + cost[u]);
	}

	
	public static void main(String args[]) throws Throwable  {
		new Thread(null,new A(),"",1<<27).start();
	}
	
	@Override
	public void run() {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);

		int n=0;
		try {
			n = sc.nextInt();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		int m=0;
		try {
			m = sc.nextInt();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		V = n;
		memo = new long[n];
		Arrays.fill(memo, -1);
		adjList = new ArrayList[n];
		g = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			adjList[i] = new ArrayList<>();
			g[i] = new ArrayList<>();
		}

		get = new long[20000];
		prefixsum = new long[20000];
		cost = new long[n];
		comp = new int[n];
		vis = new boolean[n];

		for (int i = 1; i < get.length; i++) {
			get[i] += get[i - 1] + i;
			prefixsum[i] = prefixsum[i - 1] + get[i];
		}

		for (int i = 0; i < m; i++) {
			int u=0;
			try {
				u = sc.nextInt() - 1;
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			int v=0;
			try {
				v = sc.nextInt() - 1;
			} catch (IOException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			}
			int w=0;
			try {
				w = sc.nextInt();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			adjList[u].add(new pair(v, w));

		}
		tarjanSCC();
		for (int u = 0; u < n; u++) {
			for (pair v : adjList[u]) {
				if (comp[v.x] == comp[u]) {
					cost[comp[v.x]] += get(v.y);
				} else {
					g[comp[u]].add(new pair(comp[v.x], v.y));
				}
			}
		}

		int s=0;
		try {
			s = sc.nextInt() - 1;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		pw.print(dfs(comp[s]));
		// System.out.println(Arrays.toString(cost));
		// System.out.println(SCC);
		pw.flush();
	}

	static ArrayList<pair>[] g;

	///////////////////////////////////////////////////////////////////////////////////////////

	static class tri {
		int x, y, z;

		public tri(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

	}

	static class pair implements Comparable<pair> {
		int x, y;
		boolean w, l;
		PriorityQueue<Long> pq;

		public pair(boolean a, boolean b) {
			w = a;
			l = b;
		}

		pair(int s, int d) {
			x = s;
			y = d;
		}

		@Override
		public int compareTo(pair p) {
			return Long.compare(x, p.x);
		}

		@Override
		public String toString() {
			return x + " " + y;

		}

	}

	static long mod(long ans, int mod) {
		return (ans % mod + mod) % mod;
	}

	static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	public static int log(int n, int base) {
		int ans = 0;
		while (n + 1 > base) {
			ans++;
			n /= base;
		}
		return ans;
	}

	static long pow(long b, long e) {
		long ans = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = ((ans * 1l * b));
			e >>= 1;
			{

			}
			b = ((b * 1l * b));
		}
		return ans;
	}

	static long powmod(long r, long e, int mod) {
		long ans = 1;
		r %= mod;
		while (e > 0) {
			if ((e & 1) == 1)
				ans = (int) ((ans * 1l * r) % mod);
			e >>= 1;
			r = (int) ((r * 1l * r) % mod);
		}
		return ans;
	}

	static int ceil(int a, int b) {
		int ans = a / b;
		return a % b == 0 ? ans : ans + 1;
	}

	static long ceil(long a, long b) {
		long ans = a / b;
		return a % b == 0 ? ans : ans + 1;
	}

	static HashMap<Integer, Integer> compress(int a[]) {
		TreeSet<Integer> ts = new TreeSet<>();
		HashMap<Integer, Integer> hm = new HashMap<>();
		for (int x : a)
			ts.add(x);
		for (int x : ts) {
			hm.put(x, hm.size() + 1);
		}
		return hm;
	}

	// Returns nCr % p
	static int C[];

	static int nCrModp(int n, int r, int p) {
		if (r > n - r)
			r = n - r;
		if (C[r] != 0)
			return C[r];
		// The array C is going to store last
		// row of pascal triangle at the end.
		// And last entry of last row is nCr

		C[0] = 1; // Top row of Pascal Triangle

		// One by constructs remaining rows of Pascal
		// Triangle from top to bottom
		for (int i = 1; i <= n; i++) {

			// Fill entries of current row using previous
			// row values
			for (int j = Math.min(i, r); j > 0; j--)

				// nCj = (n-1)Cj + (n-1)C(j-1);
				C[j] = (C[j] + C[j - 1]) % p;
		}
		return C[r];
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public int[] intArr(int n) throws IOException {
			int a[] = new int[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public long[] longArr(int n) throws IOException {
			long a[] = new long[n];
			for (int i = 0; i < a.length; i++) {
				a[i] = nextLong();
			}
			return a;
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	public static void shuffle(int[] times2) {
		int n = times2.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = times2[i];
			times2[i] = times2[r];
			times2[r] = tmp;
		}
	}

	

}