Goat Kart Racing Track Design

Bessie and Farmer John love goat kart racing. Their race is built on a unique farmland which is a forest of fields (nodes) connected by weighted roads (edges). In this farmland there are N fields and M roads. The farmland is composed of several farms (i.e. connected components), each containing at least two fields. In any given farm, every pair of distinct fields is connected by a unique path of roads.

Bessie plans to create a goat kart racing track by adding K new roads, each of length X, where K is the number of farms. The new roads are added in such a way that they connect the farms and form a cycle (i.e. every farm appears exactly once on the cycle). In each farm the two vertices where the new roads attach must be different (so that at least one original road is traversed within that farm). Suppose in a farm the two chosen fields have a distance d (computed along the unique path in that farm). Then the contribution from that farm is d, and the overall track length is \[ L = \Bigl(\sum_{i=1}^{K} d_i\Bigr) + K\cdot X. \] To spice up the contest, the track is considered "interesting" only if the total length L is at least Y (i.e. \(L \ge Y\)).

Two tracks are considered different if there exists at least one pair of farms that are adjacent in one track but not adjacent in the other. In other words, the ordering of farms (and the particular attachment points in each farm) matters.

Formal Problem Statement:

You are given a forest with N nodes and M edges (each with a weight), which consists of K connected components (farms). For each farm, you may choose an ordered pair of distinct vertices (u, v) and let d be the unique path distance between them in that farm. After doing so for each of the K farms, a cycle is formed by connecting these ordered pairs in a certain permutation of the farms using new roads, each of length X. The overall cycle length is \[ L = \Bigl(\sum_{i=1}^{K} d_i\Bigr) + K\cdot X. \] We say that a cycle configuration is valid (or legal) if every farm is used exactly once in the cycle and \(L \ge Y\). Compute the sum of \(L\) over all valid cycle configurations. Note that if in one track two farms are directly connected but not in another, the two tracks are considered different. (Also note that after selecting the ordered pair in each farm, the ordering of the farms on the cycle can be chosen in K! ways.)

Input Format: The first line contains four integers N, M, X, and Y. Then each of the following M lines contains three integers u, v, and w, describing an edge between nodes u and v with weight w. It is guaranteed that the given graph is a forest and that every connected component has at least two nodes.

Output Format: Output a single integer: the sum of the cycle lengths (i.e. \(L\)) over all valid configurations.

Note on Latex: All mathematical formulas are provided in \( ... \) or \[ ... \] latex format.

inputFormat

The input starts with a line containing four integers N, M, X, and Y. Each of the next M lines contains three integers u, v, and w describing an edge with weight w between nodes u and v.

outputFormat

Output a single integer — the sum of cycle lengths over all valid (interesting) cycle configurations.

sample

2 1 10 20
1 2 5

0