King's Road Maintenance

In the kingdom of New Asia there are \(N\) villages connected by \(M\) bidirectional roads. Each road is either a cobblestone road or a cement road. Due to high maintenance costs, the king has decided that only a subset of roads will be kept free. However, the free roads must satisfy the following conditions:

1. For any two villages there is exactly one path using only free roads (i.e. the free roads form a spanning tree).
2. The number of free roads is as few as possible (i.e. exactly \(N-1\) roads).
3. There must be exactly \(K\) cobblestone roads among the free roads. (Cobblestone roads are considered more "interesting" than cement roads.)

Your task is to decide whether there exists a maintenance plan (i.e. a spanning tree) satisfying the above conditions. If such a plan exists, output any one of them.

Note: Villages are numbered from 1 to \(N\). Each road connects two distinct villages.

inputFormat

The first line contains three integers \(N\), \(M\) and \(K\) \((2 \leq N \leq 10^5,\; 1 \leq M \leq 2 \times 10^5)\) — the number of villages, the number of roads, and the required number of cobblestone roads among the free ones, respectively.

Then \(M\) lines follow. Each line contains three integers \(u\), \(v\) and \(t\) \((1 \leq u,v \leq N,\; u \neq v,\; t \in \{0,1\})\). Here, \(u\) and \(v\) denote two villages connected by a road, and \(t=1\) means it is a cobblestone road while \(t=0\) indicates a cement road. There is at most one road between any pair of villages.

outputFormat

If there is a valid maintenance plan, output YES on the first line, followed by \(N-1\) lines, each containing two integers \(u\) and \(v\) representing a free road in your plan. If no valid plan exists, output NO.

sample

5 5 2
1 2 0
2 3 1
3 4 1
3 5 0
1 5 0

YES
1 5
3 5
3 4
2 3