Roads

The Kingdom of New Asia has $N$ villages connected by $M$ roads. Some roads are paved with gravel and others with concrete. Keeping every road toll-free is far too expensive, so the king decides on a new road-maintenance plan.

The king wants the number of free roads to be as small as possible, while still guaranteeing that between any two villages there is exactly one path using only free roads. In other words, the free roads must form a single tree that connects all villages. Moreover, because the king enjoys walking on gravel, he wants exactly $K$ of the free roads to be gravel roads.

For example, suppose the villages and roads are as in Figure 1a. If the king wants exactly $2$ free gravel roads, then making roads $(1, 2), (2, 3), (3, 4), (3, 5)$ free (Figure 1b) satisfies the requirements: (1) all villages are connected by free roads, (2) the number of free roads is as small as possible, and (3) exactly two of them, namely $(2, 3)$ and $(3, 4)$, are gravel. Because such a plan exists, the answer in this case is possible.

Figure 1: (a) An example of the villages and roads of New Asia. Solid lines are concrete roads and dashed lines are gravel roads. (b) A maintenance plan with exactly two free gravel roads; only the free roads are shown.

Given the roads of the kingdom and the number $K$ of free gravel roads the king wants, write a program that decides whether a maintenance plan meeting the king's requirements exists.

The first line contains three space-separated integers.

• $N$: the number of villages ($1 \le N \le 20\,000$)
• $M$: the number of roads ($1 \le M \le 100\,000$)
• $K$: the number of gravel roads the king wants to keep free ($0 \le K \le N-1$)

Each of the next $M$ lines describes road $i$ (for $i$ from $1$ to $M$); line $(i+1)$ describes road $i$ with three space-separated integers.

• $u_i$ and $v_i$: the two villages connected by road $i$ (villages are numbered $1$ to $N$)
• $c_i$: the type of road $i$; $c_i = 0$ means a gravel road and $c_i = 1$ means a concrete road.

There is at most one road between any pair of villages.

Print possible on a single line if a maintenance plan meeting the king's requirements exists, and no solution otherwise.