免费道路

题目描述

新亚（$New$ $Asia$）王国有$N$个村庄，由$M$条道路连接。其中一些道路是鹅卵石路，而其它道路是水泥路。保持道路免费运行需要一大笔费用，并且看上去王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。

国王已决定保持尽可能少的道路免费，但是两个不同的村庄之间都应该一条且仅由一条免费道路的路径连接。同时，虽然水泥路更适合现代交通的需要，但国王也认为走在鹅卵石路上是一件有趣的事情。所以，国王决定保持刚好$K$条鹅卵石路免费。

还需要满足：

1. 两个村庄之间都有一条由免费道路组成的路径。
2. 免费的道路已尽可能少。

给定一个关于新亚王国村庄和道路的述以及国王决定保持免费的鹅卵石道路数目，写一个程序确定是否存在一个道路维护计划以满足国王的要求，如果存在则任意输出一个方案。

输入格式

输入第一行包含三个由空格隔开的整数：村庄的数目$N$，道路的数目$M$，国王希望保持免费的鹅卵石道路数目$K$。

此后$M$行述了新亚王国的道路，编号分别为$1$到$M$。第$(i+1)$行述了第$i$条道路的情况。

用三个由空格隔开的整数述：分别是$u_{i}$，$v_{i}$，$c_{i}$，$(u_{i},v_{i})$为第$i$条道路连接的两个村庄的编号，村庄编号为$1$到$N$；$c_{i}$表示第$i$条道路的类型，$c_{i}=0$表示第$i$条道路是鹅卵石路，$c_{i}=1$表示第$i$条道路是水泥路。

输入数据保证一对村庄之间至多有一条道路连接。

输出格式

如果满足国王要求的道路维护方案不存在，你的程序应该在输出第一行打印no solution。否则，你的程序应该输出一个符合要求的道路维护方案，也就是保持免费的道路列表。按照输入中给定的那样输出免费的道路。如果有多种合法方案，你可以任意输出一种。

数据范围与提示

• 对于$20\%$的数据，有$1 \leq N \leq 1000$，$1 \leq M \leq 3000$；
• 对于$100\%$的数据，有$1 \leq N \leq 2 \times 10^{4}$，$1 \leq M \leq 10^{5}$，$0 \leq K \leq N-1$。

样例

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

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