Parity Constraint Perfect Matching

Gukryeol wants to set one more Parity Constraint problem out of respect for a graduated senior.

A bipartite graph is given with $N$ vertices on the left, $N$ vertices on the right, and $M$ weighted edges. Vertices on each side are numbered 1 to $N$, and there is at most one edge between any pair of vertices.

A Perfect Matching is a set of $N$ edges that share no endpoints. Find one Perfect Matching whose weight sum is even and one whose weight sum is odd.

The first line contains $N$ and $M$. ($1 \le N \le 500$, $1 \le M \le N^2$)

Each of the next $M$ lines contains $(x, y, c)$ in order. $x$ is the left vertex number, $y$ is the right vertex number, and $c$ is the edge weight. ($1 \le x, y \le N$, $1 \le c \le 10^9$) No two vertices are connected by more than one edge.

Print $N$ lines with the edges of a Perfect Matching whose weight sum is even, giving the left and right endpoint numbers in that order. If no such matching exists, print -1.

From the second line on, print the same way for a Perfect Matching whose weight sum is odd. If none exists, print -1.

The weight sum does not need to be minimal, and the edges may be printed in any order. If several answers exist, print any of them.