小红的染色生成树
题号：NC318117
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}给定一个包含 n 个结点，m 条边的简单无向图（保证所给图连通），其中每条边都被染为了 0,1,2 三种颜色的一种。
\hspace{15pt}现在小红希望找到一棵所给图的生成树，其中恰好包含了两种颜色的边。
\hspace{15pt}请你找到一棵合法的生成树，或输出 -1，代表不存在合法的生成树。

【名词解释】
\hspace{15pt}简单无向图：指不包含自环（连接节点自身的边）和重边（两个节点之间存在多条边）的无向图。即任意两个不同节点之间至多只有一条边。
\hspace{15pt}生成树：对于一张由 n 个节点构成的连通图，选出 n-1 条边将所有节点连通，这些边会组成一棵树，称为这张图的一棵生成树。

输入描述:

\hspace{15pt}第一行输入两个整数 n, m\left(2 \leq n \leq 10^5 ,n - 1 \leq m \leq \min\left(2\times10^5, \lfloor\tfrac{n\times \left(n - 1\right)}{2}\rfloor\right)\right)。
\hspace{15pt}之后的 m 行，每行输入三个整数 u_i,v_i,w_i\left(1 \leq u_i, v_i \leq n, u_i \ne v_i, w_i \in\{0,1,2\}\right)，代表在结点 u_i,v_i 之间连有一条颜色为 w_i 的边。

输出描述:

\hspace{15pt}如果不存在合法的生成树，请输出 -1；否则输出 n - 1 行，每行两个整数 u_i, v_i，代表生成树包含连接 u_i, v_i 的边。

\hspace{15pt}如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1

输入

复制 
3 3
1 2 0
2 3 1
3 1 2

输出

复制 
1 2
2 3
示例2

输入

复制 
3 3
1 2 0
2 3 0
3 1 0

输出

复制 
-1