4438: Minimum Spanning Tree

Bobo has an undirected connected graph with n vertices and m edges, where the i-th edge is associated with two parameters ai and bi.

Let f(x) be the sum of weights of the edges in the minimum spanning tree when the weight of the i-th edge is ai + bi ⋅ x, your task is to calculate the value of min (f(l), f(l + 1), …, f(r)).

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains four integers n, m, l and r, indicating the number of vertices, the number edges and the range of x.

For the next m lines, the i-th line contains four integers ui, vi, ai and bi , indicating that the i-th edge connects vertices ui and vi and the parameters of the i-th edge. It is guaranteed that the graph is connected.

• 2 ≤ n ≤ 10⁵
• n − 1 ≤ m ≤ 2 × 10⁵
• 0 ≤ l ≤ r ≤ 10⁶
• 1 ≤ ui, vi ≤ n, ui ≠ vi
• 1 ≤ ai ≤ 10⁶
• − 10⁶ ≤ bi ≤ 10⁶
• The sum of n does not exceed 10⁶.
• The sum of m does not exceed 2 × 10⁶.

5 6 1 5
1 2 3 1
2 3 5 -1
3 4 1 2
4 5 1 -1
5 1 5 3
2 4 3 -1
5 6 1 5
1 2 1 1
2 3 1 2
3 4 1 -10
3 4 2 10
5 1 3 10
2 4 5 -10

2
-35