Triple tree

For an integer $k$ greater than 1, infinitely many triples of positive integers $(a, b, c)$ satisfy $a^2 + b^2 + c^2 = k(ab + bc + ca) + 1.$

The triple $(1, k, k + k^2)$ satisfies the equation. If a triple $(a, b, c)$ with $a < b < c$ satisfies it, then the two triples $(b,\; c,\; k(b + c) - a), \qquad (a,\; c,\; k(a + c) - b)$ satisfy it as well, and each of them is already written in increasing order. Let $S$ be the set of all triples obtained from $(1, k, k + k^2)$ by repeating these two operations.

List the triples of $S$ in increasing order of their largest number. When two triples share the same largest number, the one with the smaller middle number comes first, and when the middle numbers are equal too, the one with the smaller smallest number comes first. Walk through the triples in this order, keeping a set $U$ of the numbers printed so far. When none of the three numbers is in $U$, print the triple and add its three numbers to $U$. When at least one of them is in $U$, skip the triple. Find the first $n$ triples printed this way.

The $3n$ printed numbers are pairwise distinct, and none of them has more than 100 digits.

The first line contains the integers $k$ and $n$, separated by a space. ($2 \le k \le 1000$, $1 \le n \le 1000$)

Print $n$ lines, giving the triples in the order defined above. On each line print the three numbers of one triple in increasing order, separated by spaces.