Three-Way Call

Korea Telecom provides a three-way calling service, where three people can be connected in one call. Its telephone network consists of switches connected by bidirectional links, and each caller accesses the network through one switch. All switches in the network are connected, so a person connected to any switch can call a person connected to any other switch. Each link has a given usage cost.

Given the three switches used by the callers, choose links that connect all three switches with the minimum possible total cost. Write a program that outputs the minimum cost and the links used.

The first line contains two integers n and m. n is the number of switches in the telephone network, with 1 <= n <= 1000. m is the number of links between switches. There is at most one direct link between the same pair of switches. The switches are numbered from 1 to n.

Each of the next m lines describes one link. A line contains the numbers of the two switches connected by the link, followed by the cost of using that link. The cost is a positive integer less than 100.

The last line contains the three switch numbers used by the callers. The three numbers are all distinct.

On the first line, output the minimum total cost needed to connect the three callers, followed by the number of selected links.

Then output one selected link per line, giving the two switch numbers at its endpoints. If there are multiple minimum-cost ways to connect the callers, output any one of them.