F. Portal Maintenance
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a galaxy far, far away, humanity has successfully established civilization across multiple planets within a star system. This system, which contains $$$n$$$ planets, is connected by a network of $$$n-1$$$ portals. These portals enable swift and efficient travel between the planets, ensuring that every planet is accessible from any other. The technology that powers these portals is sophisticated and advanced, but like all technology, it requires maintenance and upgrades to keep functioning optimally.

Isaac, a skilled electrician known for his expertise in portal technology, is tasked with a crucial mission. The central administration unit has decided that it's time to upgrade the firmware of all the portals in the star system to improve their performance and security. To accomplish this, all the portals need to be disabled temporarily first, which is precisely his mission.

Before disabling a portal, Isaac must first test its functionality by traveling through it at least once. But to avoid the risk of forgetting to disable any portal, Isaac decides that once he travels through a portal, he will immediately disable that portal. And since a disabled portal cannot be used for traveling, it means that he can only use each portal once. This creates a problem: how can he disable all the portals and still return back? The more he thinks about it, the more he realizes that it's impossible to achieve this without some form of intervention.

Fortunately, Isaac has a powerful tool at his disposal: a jammer. This device allows him to travel through portals even after they've been disabled. However, the jammer comes with a significant cost. Each time Isaac activates the jammer, it costs $$$c$$$, and for every portal he travels through while the jammer is activated, it costs $$$w_i$$$ to travel through the $$$i$$$-th portal (even if the portal is not disabled). Importantly, while the jammer is active, Isaac cannot disable any portals, meaning he must deactivate the jammer before he can continue disabling portals. Moreover, Isaac can only activate the jammer a limited number of times — at most $$$\frac{n}{2}$$$ times.

You are tasked to help Isaac find the minimum possible cost to disable all the portals, starting and ending at planet $$$1$$$. Additionally, you need to identify the optimal planets where he should activate and deactivate the jammer to achieve this goal.

Input

The first line of input contains two integers $$$n$$$, $$$c$$$ ($$$1 \le n,c \le 10^6$$$), denoting the total number of planets in the system and the initiation cost for each activation.

Each of the next $$$n-1$$$ lines contains three integers, $$$u$$$, $$$v$$$, and $$$w$$$, denoting a portal between planet $$$u$$$ and planet $$$v$$$ with cost $$$w$$$ to use it during the jammer activation. ($$$1\le u \lt v\le n , 1 \le d \le 10^6$$$).

Output

On the first line, output $$$W$$$ and $$$k$$$, the minimum cost and how many times the jammer is used, respectively.

On each of the next $$$k$$$ lines, output two integers $$$u, v$$$ denoting for Isaac to activate the jammer on planet $$$u$$$ and deactivate on planet $$$v$$$ ($$$1\le u, v\le n$$$).

If there are more than one possible way to use the jammer, output any of them. Print -1 if it is impossible to do so.

Examples
Input
3 1
1 2 1
2 3 1
Output
3 1
3 1
Input
5 2
1 2 1
2 3 2
2 4 1
2 5 3
Output
11 2
5 4
3 1
Note

In the second example, one of the possible routes is as follows:

  • From planet $$$1$$$, he uses portal $$$1$$$ to travel to planet $$$2$$$ and disables the portal.
  • From planet $$$2$$$, he uses portal $$$4$$$ to travel to planet $$$5$$$ and disables the portal.
  • At planet $$$5$$$, he activates the jammer, then travels to planet $$$2$$$ through portal $$$4$$$, then to planet $$$4$$$ through portal $$$3$$$ and deactivates the jammer at planet $$$4$$$, costing $$$2+3+1=6$$$.
  • From planet $$$4$$$, he uses portal $$$3$$$ to travel to planet $$$2$$$ and disables the portal.
  • From planet $$$2$$$, he uses portal $$$2$$$ to travel to planet $$$3$$$ and disables the portal.
  • At planet $$$3$$$, he activates the jammer, then travels to planet $$$2$$$ through portal $$$2$$$, then to planet $$$1$$$ through portal $$$1$$$ and deactivates the jammer at planet $$$1$$$, costing $$$2+2+1=5$$$. The total cost is $$$6+5=11$$$.