Minimum Road Repair

In a kingdom with n cities and m roads, there were at most one direct road between any two cities. After a severe war, d roads were destroyed. Two important cities, A and B, have lost connectivity. The king wants to repair some of the destroyed roads so that the connectivity between A and B is restored, and the total repair cost (i.e. the sum of the lengths of the repaired roads) is minimized.

You are given the details of the roads. Each road is described by its endpoints, its length, and its state. If a road is intact, it can be used without repair (cost 0). If a road is destroyed, you may choose to repair it at a cost equal to its length. Your task is to compute the minimum total repair cost required to reconnect city A and city B. If it is impossible to restore the connection, output -1.

Note: All formulas are in LaTeX format where applicable. For instance, the number of cities, roads, and destroyed roads are given as $n$, $m$, and $d$, respectively.

inputFormat

The first line contains five integers: n m d A B, where:

• $n$ is the number of cities.
• $m$ is the total number of roads.
• $d$ is the number of destroyed roads (among the $m$ roads, exactly $d$ are destroyed).
• A and B are the labels of the two important cities that must be connected.

The next m lines each contain four integers: u v l s, where:

• u and v are the endpoints (cities) connected by the road.
• l is the length of the road (i.e. the cost if it is destroyed).
• s indicates the state of the road: 0 means the road is intact, and 1 means it is destroyed.

outputFormat

Output a single integer representing the minimum total repair cost required to restore connectivity between city A and city B. If no such connection exists, output -1.

sample

4 4 1 1 4
1 2 5 0
2 3 6 0
3 4 4 0
1 4 20 1

0