Problem: On the Berland Dependence Day it was decided to organize a great marathon. Berland consists of n cities, some of which are linked by two-way roads. Each road has a certain length. The cities are numbered from 1 to n. It is known that one can get from any city to any other one by the roads.

n runners take part in the competition, one from each city. But Berland runners are talkative by nature and that's why the juries took measures to avoid large crowds of marathon participants. The jury decided that every runner should start the marathon from their hometown. Before the start every sportsman will get a piece of paper containing the name of the city where the sportsman's finishing line is. The finish is chosen randomly for every sportsman but it can't coincide with the sportsman's starting point. Several sportsmen are allowed to finish in one and the same city. All the sportsmen start simultaneously and everyone runs the shortest route from the starting point to the finishing one. All the sportsmen run at one speed which equals to 1.

After the competition a follow-up table of the results will be composed where the sportsmen will be sorted according to the nondecrease of time they spent to cover the distance. The first g sportsmen in the table will get golden medals, the next s sportsmen will get silver medals and the rest will get bronze medals. Besides, if two or more sportsmen spend the same amount of time to cover the distance, they are sorted according to the number of the city where a sportsman started to run in the ascending order. That means no two sportsmen share one and the same place.

According to the rules of the competition the number of gold medals g must satisfy the inequation g1 ≤ g ≤ g2, where g1 and g2 are values formed historically. In a similar way, the number of silver medals s must satisfy the inequation s1 ≤ s ≤ s2, where s1 and s2 are also values formed historically.

At present, before the start of the competition, the destination points of every sportsman are unknown. However, the press demands details and that's why you are given the task of counting the number of the ways to distribute the medals. Two ways to distribute the medals are considered different if at least one sportsman could have received during those distributions different kinds of medals.

Input

The first input line contains given integers n and m (3 ≤ n ≤ 50, n - 1 ≤ m ≤ 1000), where n is the number of Berland towns and m is the number of roads.

Next in m lines road descriptions are given as groups of three integers v, u, c, which are the numbers of linked towns and its length (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ c ≤ 1000). Every pair of cities have no more than one road between them.

The last line contains integers g1, g2, s1, s2 (1 ≤ g1 ≤ g2, 1 ≤ s1 ≤ s2, g2 + s2 < n). The input data numbers, located on one line, are space-separated.

Output

Print the single number — the number of ways to distribute the medals. It is guaranteed that the number fits in the standard 64-bit signed data type.

Examples

Input

3 2
1 2 1
2 3 1
1 1 1 1


Output

3


Input

4 5
1 2 2
2 3 1
3 4 2
4 1 2
1 3 3
1 2 1 1


Output

19


Input

3 3
1 2 2
2 3 1
3 1 2
1 1 1 1


Output

4

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author AlexFetisov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskH solver = new TaskH();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskH {

    public static final int INF = Integer.MAX_VALUE / 2;

    long[][] g;
    int n;
    int G1, G2, S1, S2;
    int[] min;
    int[] max;
    int[] minId;
    int[] maxId;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        n = in.nextInt();
        int m = in.nextInt();
        g = new long[n][n];
        ArrayUtils.fill(g, INF);
        for (int i = 0; i < m; ++i) {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            int c = in.nextInt();
            g[x][y] = g[y][x] = c;
        }
        for (int i = 0; i < n; ++i) g[i][i] = 0;
        g = Floyd.floyd(g);
        G1 = in.nextInt();
        G2 = in.nextInt();
        S1 = in.nextInt();
        S2 = in.nextInt();
        min = new int[n];
        max = new int[n];
        minId = new int[n];
        maxId = new int[n];
        Arrays.fill(min, INF);
        Arrays.fill(max, -INF);
        for (int i = 0; i < n; ++i) {
            minId[i] = i;
            maxId[i] = i;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue;
                min[i] = (int) Math.min(min[i], g[i][j]);
                max[i] = (int) Math.max(max[i], g[i][j]);
            }
        }
        long res = 0;
        for (int g = 0; g < n; ++g) {
            for (int s = 0; s < n; ++s) {
                if (g != s) {
                    res += f(g, s);
                }
            }
        }
        out.println(res);
    }

    long f(int goldId, int silverId) {
        if (min[goldId] > max[silverId]) return 0;
        long[][][] dp = new long[n + 1][n + 1][n + 1];
        dp[0][0][0] = 1;
        for (int i = 0; i < n; ++i) {
            int mask = 0;
            if (i == goldId) {
                mask |= 1;
            } else if (i == silverId) {
                mask |= 4;
            } else {
                for (int f = 0; f < n; ++f) {
                    if (f != i) {
                        if (compare(g[i][f], i, min[goldId], goldId) < 0) {
                            mask |= 1;
                        } else if (compare(g[i][f], i, max[silverId], silverId) > 0) {
                            mask |= 4;
                        } else {
                            mask |= 2;
                        }
                    }
                }
            }
            for (int g = 0; g <= i + 1; ++g) {
                for (int s = 0; s <= i + 1; ++s) {
                    if (g + s > i + 1) break;
                    if (BitUtils.checkBit(mask, 0) && g > 0) {
                        dp[i + 1][g][s] += dp[i][g-1][s];
                    }
                    if (BitUtils.checkBit(mask, 1) && s > 0) {
                        dp[i + 1][g][s] += dp[i][g][s-1];
                    }
                    if (BitUtils.checkBit(mask, 2)) {
                        dp[i + 1][g][s] += dp[i][g][s];
                    }
                }
            }
        }
        long res = 0;
        for (int i = G1; i <= G2; ++i) {
            for (int j = S1; j <= S2; ++j) {
                res += dp[n][i][j];
            }
        }
        return res;
    }

    private int compare(long di, int i, int dj, int j) {
        if (di != dj) {
            return (int) (di - dj);
        } else {
            return i - j;
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer stt;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
    }

    public String nextLine() {
        try {
            return reader.readLine().trim();
        } catch (IOException e) {
            return null;
        }
    }

    public String nextString() {
        while (stt == null || !stt.hasMoreTokens()) {
            stt = new StringTokenizer(nextLine());
        }
        return stt.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

}

class ArrayUtils {

    public static void fill(long[][] a, int value) {
        for (int i = 0; i < a.length; ++i) {
            Arrays.fill(a[i], value);
        }
    }

}

class Floyd {

    public static long[][] floyd(long[][] g) {
        int n = g.length;
        long[][] d = new long[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = g[i][j];
                if (i == j) d[i][j] = 0;
            }
        }
        for (int m = 0; m < n; ++m) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    d[i][j] = Math.min(d[i][j], d[i][m] + d[m][j]);
                }
            }
        }

        return d;
    }
}

class BitUtils {
    public static boolean checkBit(int mask, int bit) {
        return (mask & (1 << bit)) > 0;
    }

}