A higher resolution is required to access the IDE

- 59

## Statement

## Goal

Edison is bringing electricity to`N`houses. He has already set up a power generator in house 1 and wants to connect it to the other houses. There are

`M`pairs of houses that can be connected together, and we know how much making a link between each pair costs. Your job is to find which houses to link so that all the houses are connected to house 1 (directly or through other houses), while minimizing the total cost.

* **there is always a solution that connects all houses**

* **the total distance from the generator to a house does not matter, as long as there is a path between them**

Input

**Line 1:**two integers,

`N`and

`M`, respectively the number of houses, and the number of connectable pairs

**Next**three integers

`M`lines`House1`,

`House2`and

`Cost`representing a possible connection between two houses

Output

**Line 1:**two integers,

`K`and

`C`, respectively the number of connections to make, and the total cost

**Next**the connections, as given, numerically sorted (on House1, then on House2)

`K`lines:Constraints

1 ≤

0 ≤

1 ≤

`N`≤ 50000 ≤

`M`≤ 500001 ≤

`House1`,`House2`, ≤`N`Example

Input

3 3 1 2 1 2 3 99 1 3 7

Output

2 8 1 2 1 1 3 7

A higher resolution is required to access the IDE