## CCC '18 S5 - Maximum Strategic Savings

View as PDF

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem type
##### Canadian Computing Competition: 2018 Stage 1, Senior #5

A long time ago in a galaxy far, far away, there are planets numbered from to . Each planet has cities numbered from to . Let city of planet be denoted as .

There are two-way flights in the galaxy. For every planet , there are flights numbered from to . Flight connects cities and and costs energy daily to maintain.

There are two-way portals in the galaxy. For all cities with number , there are two-way portals numbered from to . Portal connects cities and and costs energy daily to maintain.

It is possible to travel between any two cities in the galaxy using only flights and/or portals.

Hard times have fallen on the galaxy. It was decided that some flights and/or portals should be shut down to save as much energy as possible, but it should remain possible to travel between any two cities afterwards.

What is the maximum sum of energy that can be saved daily?

#### Input Specification

The first line contains four space-separated integers , , , .

Then lines follow; the -th one contains three space-separated integers , , .

Then lines follow; the -th one contains three space-separated integers , , .

It is guaranteed that it will be possible to travel between any two cities using flights and/or portals. There may be multiple flights/portals between the same pair of cities or a flight/portal between a city and itself.

For of the available marks, , for all , and for all .

For an additional of the available marks, .

For an additional of the available marks, .

#### Output Specification

Output a single integer, the maximum sum of energy that can be saved daily.

#### Sample Input

2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 5

#### Sample Output

41

#### Explanation for Sample Input

One possible way is to shut down the flights between cities and , and , and , and , and , and shut down the portal between cities and for total energy savings of .