Problem D
Cut the Negativity

Image by Pattarisara Suvichanarakul (iStock); Used under license

An airline tracks costs of flights between $n$ different cities in a table. The cities are numbered from $1$ to $n$. In the table, the entry in $\textrm{row}~ i$ and $\textrm{column}~ j$ represents the cost of a direct flight from $\textrm{city}~ i$ to $\textrm{city}~ j$. However, if there is no direct flight between these two cities, then a value of $-1$ is displayed in the table. A manager for the airline has decided that the table is too hard to read with all the $-1$ values; she does not like all the negativity. Instead, she would prefer a list of the flight prices for just the cities for which there are direct flights. Each entry in the list should specify the city from which the flight departs, the city at which the flight lands, and the price for the flight. The list should be sorted in increasing order by departure city, and if there is more than one flight departing from a city, then ties should be broken by the arrival city in increasing order. For example, the table on the left below should be turned into the list on the right. This matches the first sample input/output.

Input

The first line of input consists of an integer, $n$ ($2 \leq n \leq 100$), the number of cities. This is followed by $n$ lines, each consisting of $n$ space-separated integers, where the $j^{\text {th}}$ value on the $i^{\text {th}}$ line indicates the cost of the flight from $\textrm{city}~ i$ to $\textrm{city}~ j$. A value of $-1$ is used to indicate that there is no direct flight from $\textrm{city}~ i$ to $\textrm{city}~ j$. It is guaranteed that there is no direct flight departing from and arriving at the same city. All costs will be strictly positive integers less than $10\, 000$. It is guaranteed that there will be at least one direct flight represented in the table.

Output

The first line of output is the number of direct flights, $m$. This is to be followed by $m$ lines of the form $u$ $v$ $c$, indicating that there is a direct flight from $\textrm{city}~ u$ to $\textrm{city}~ v$ with a cost of $\textrm{of}~ c$. These must be printed in ascending order, sorted by departure city number with ties broken by the arrival city number.

4
-1 1 -1 2
9 -1 -1 -1
-1 3 -1 4
7 1 2 -1

8
1 2 1
1 4 2
2 1 9
3 2 3
3 4 4
4 1 7
4 2 1
4 3 2

3
-1 -1 -1
15 -1 -1
2 2 -1

3
2 1 15
3 1 2
3 2 2