Ticket Swapping (Small)

The city opened its first subway line. It has $N$ stations, and fares are charged with entry cards.

A passenger takes an entry card when boarding. The card records the station where the passenger boarded. To leave the subway the passenger hands the card back and pays according to the distance, counted in stations traveled, between the station written on the card and the station where the card is handed back.

• If the two stations are the same, the fare is 0 pounds.
• If they are adjacent, the fare is $N$ pounds.
• If the distance is two stations, the fare is $2N - 1$ pounds: $N$ for the first station and $N - 1$ for the second.
• The third station costs $N - 2$, so a three station ride costs $3N - 3$. The fourth station costs $N - 3$, and the $i$th station costs $N + 1 - i$.
• Riding from one end of the line to the other covers $N - 1$ stations. The last of them costs 2 pounds, and the whole ride costs $\frac{N^2 + N - 2}{2}$ pounds.

After the system started, the city found its revenue smaller than expected. Passengers were swapping entry cards. Suppose one passenger boards at station $A$, rides two stations and leaves at $B$, while another boards at $B$, rides three stations and leaves at $C$. Together they would pay $2N - 1 + 3N - 3 = 5N - 4$. If the two swap cards at station $B$, the first one hands back a card that reads $B$ while leaving station $B$, so the recorded distance is 0 and the ride is free. The second one hands back a card that reads $A$ while leaving station $C$, a distance of 5 stations, and pays $5N - 10$. The city loses 6 pounds.

The city wants to know how much it can lose if this becomes common. Consider only one direction of the line, from station 1 to station $N$ through every station in order, and only one train. A passenger who rides from station $o$ to station $e$ receives an entry card at $o$, and can swap that card any number of times with any other passenger anywhere between $o$ and $e$, including passengers who leave at $o$ and passengers who board at $e$. The passenger then leaves the train at $e$ and hands back some card. Handing back a card is required in order to leave. A passenger never gets off the train in between, so nobody hands back a card and takes a new one during a ride.

You are given a traffic table that says how many passengers ride from which station to which. Compute the money the city loses when passengers swap cards to make that loss as large as possible.

The first line has the number of test cases $T$. Each test case begins with a line holding the number of stations $N$ and the number of records $M$. Stations are numbered 1 through $N$. Each of the next $M$ lines has three integers $o_i$, $e_i$ and $p_i$, meaning that $p_i$ passengers ride from station $o_i$ to station $e_i$.

Limits

• $1 \le T \le 20$
• $2 \le N \le 100$
• $1 \le M \le 100$
• $1 \le o_i < e_i \le N$
• $1 \le p_i \le 100$

The same pair $(o_i, e_i)$ can appear on more than one line.

For each test case print one line in the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the largest loss the city can suffer from card swapping, modulo 1000002013.

In the first test case of the example, the two passengers meet at station 3 and swap cards, which is the situation described in the statement. In the second test case the two passengers never meet, so they cannot swap and the city loses nothing. In the third test case only one of the two earlier passengers can swap with the later passenger.