Minimum frame

Plus

Problem description Progress

ID 33230. School

Темы: Minimum frame Algorithms on graphs

In order to prepare for the Olympiad in Informatics, the mayor decided to provide all schools in the city with reliable power supply. To do this, it is necessary to conduct a power line from an alternative source of electricity “Maibuttya” to one of the schools in the city (it doesn’t matter which one), as well as to connect some schools with each other by power lines.

A school is considered to have a reliable power supply if it is directly connected to the Maibutcha source, or to one of those schools that has a reliable power supply.

The connection cost between some pairs of schools is known. The mayor of the city decided to choose one of the two most economical power supply schemes (the cost of the scheme is equal to the sum of the costs of connecting pairs of schools).

Write a program that calculates the cost of the two most cost-effective alternative power supply schemes for schools.

Input

The first line of the input file contains two natural numbers separated by a space: N (3 <= N <= 100), the number of schools in the city, and

M – the number of possible connections between them. Each of the following M lines contains three numbers: A_i, B_i, C_i, separated by spaces, where C_i - cost of laying a power line (1 <= C_i <= 300) from school A_i to school B_i (i=1,2,…,N).



 

Output

The single line of the output file must contain two natural numbers S₁ and S₂ separated by a space &ndash ; the two lowest circuit costs (S₁ <= S₂). S₁=S₂ if and only if there are several least cost reliable power supply schemes.

 

It is guaranteed that there are two different reliable power supply schemes for the input data.

 
Examples




#
Input
Output




1

5 8

1 3 75

3 4 51

2 4 19

3 2 95

2 5 42

5 4 31

1 2 9

3 5 66

110 121

ID 38132. Portals

Темы: Disjoint set system Tree Data Structures Minimum frame

Besi is located on a network of N (2≤N≤10⁵) vertices labeled 1…N and 2N portals labeled 1…2N. Each portal connects two different vertices u and v (u≠v). A set of portals can connect some pair of vertices.
Each vertex v is adjacent to four different portals. The list of portals of v is given by pv=[p_v,1,p_v,2,p_v,3,p_{v ,4}].

Your current position can be represented by an ordered pair (current vertex,current portal); that is, a pair (v,p_v,i) where 1≤v≤N and 1≤i≤4. You can use one of the following operations to change your current position:

Change the current vertex by moving through the current portal.
Switch current portal. At each vertex, the first two portals in the list are paired and the last two portals in the list are also paired. So if your current state is (v,p_v,2), then you can switch to use the portal (v,p_v,1) and back. Similarly, if your current position is (v,p_v,3) you can switch to the portal (v,p_v,4) and back. no other switching is allowed (eg you cannot switch from portal pv,2 to portal) p_v,4).
There are 4N different states in total. Unfortunately, it may not be that any state is reachable from any state by a sequence of given operations. Therefore, for the cost of cv (1≤c_v≤1000) moons, you can rearrange the list of portals adjacent to v, in any order you wish. After that, the first two portals in the list are combined into one pair, and the last two portals into another pair.

For example, if you rearrange the portals of v in the order [p_v,3,p_v,1,p_v,2,p_v,4], This means. what if you are at top v,

If you are in the p_v,1 portal, you can switch to the p_v,3 portal and back
If you are in the p_v,2 portal, you can switch to the p_v,4 portal and back
Now you cannot switch from portal p_v,1 to p_v,2, or from portal p_v,3 to portal p_v,4 and vice versa.
Calculate the minimum number of moons required to modify the network in such a way as to make each state reachable from each state. It is guaranteed that the test data is constructed in such a way that there is at least one way to modify the network in this way.

Input:
The first line contains N.
Each of the next N lines describes a vertex. The string v+1 contains 5 space-separated integers c_v,p_v,1,p_v,2,p_{v ,3},p_v,4.
It is guaranteed that for each v all p_v,1,p_v,2,p_v,3,p_v,4 are distinct, and each portal appears in the lists of exactly two vertices.

Output:
One line contains the minimum number of moons required to modify the network to make each state reachable from another state.

Examples

#	Input	Output	Explanation
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	It is enough to swap lists of vertices 1 and 4. This requires c1+c4=13 muns. The permutations are: p1=[1,9,4,8] and p4=[7,4,6,3].