Many countries dream of capturing great and glorious country of Berland. Berland is a big country consisting of N cities, some of them are connected by bidirectional roads. Each pair of cities is connected by no more then one road. A traveler can get from one city to any other city traveling by the roads only.

Invaders plan to use these roads during their operation, but Berland military forces are strong enough to destroy an enemy trying to move along the roads. The treacherous plan was developed to make the invasion easier: Berland should be divided into two parts. To make the plan more effective the decision was made to use terrorists from the Berland opposition. Several groups agreed to participate in the plan. The terrorists' resources are limited, so they can only destroy roads, not cities. The procedure of the road destruction is a costly operation. The security precautions on different roads can vary, so the cost of the road destruction can be different.

Invaders want to suddenly attack Berland without declaring the war and quickly capture one of the cities. Berland troops can't move through the captured city as they can't move along the destroyed roads.

Your task is to find cheapest plan of roads destruction, so that at least one city exists which can be captured and allow invaders to divide the country into two parts. Berland is considered divided, if two such cities exist, that there is no way along non-destroyed roads and through non-captured cities from one to another.

The first line of the input contains two integer numbers N and M (3 ≤ N ≤ 50; 1 ≤ M ≤ 500), where N is the number of cities and M is the number of roads. The following M lines contain the description of the roads given as three integer numbers a_i, b_i, w_i (1 ≤ a_i < b_i ≤ N; 1 ≤ w_i ≤ 10). The cost of destruction of the the road from a_i to b_i is w_i.

Write to the first line the total amount of money required to destroy roads in the optimal plan. Write to the second line K — number of roads to be destroyed according to the plan. Write to the third line numbers of roads to be destroyed divided by one space. The roads are numbered in order of appearance in the input. If there are several solutions, choose any of them.

sample input	sample output
3 3 1 2 1 2 3 2 1 3 2	1 1 1

sample input	sample output
4 6 1 2 1 1 3 1 2 3 2 1 4 1 2 4 2 3 4 3	2 2 2 4