Ticket Swapping

The city opened its first subway line. It has $N$ stations, numbered 1 to $N$, and fares are charged through entry cards instead of tickets.

A passenger entering the subway receives one entry card, which records the station where the passenger entered. On the way out the passenger has to give up an entry card, and pays according to the distance between the station printed on the card and the station where the card is surrendered.

• If the two stations are the same, the passenger pays nothing.
• If they are adjacent, the passenger pays $N$ pounds.
• If the distance is two stations, the passenger pays $2N - 1$: a charge of $N$ for the first stop and $N - 1$ for the second.
• The third stop costs $N - 2$, so a three station trip costs $3N - 3$. The fourth stop costs $N - 3$, and the $i$-th stop costs $N + 1 - i$.
• Travelling from one end of the line to the other (a distance of $N - 1$ stations) therefore costs 2 pounds for the last station and $(N^2 + N - 2) / 2$ in total.

After introducing this system the city noticed that its revenue was smaller than expected. The cause was passengers swapping entry cards. Suppose one person enters at station $A$, travels two stations and leaves at station $B$, while another person enters at station $B$, travels three stations and leaves at station $C$. Normally the two pay $2N - 1 + 3N - 3 = 5N - 4$ in total. If they swap their cards at station $B$, the first person surrenders a card printed with $B$ at station $B$, registers a distance of zero and travels for free. The second person surrenders a card printed with $A$ at station $C$, a distance of 5 stations, and pays $5N - 10$. The city loses six pounds.

The city wants to know how much it can lose if this practice becomes widespread. Consider only one direction of the line (from station 1 to station $N$, passing through every station in order) and only one train. A passenger travelling from $o$ to $e$ obtains a card at $o$, 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 enter at $e$, and then leaves at $e$ after surrendering some card. Surrendering a card is required in order to leave. A passenger never leaves the train in the middle, so nobody surrenders the card being held and obtains a new one.

You are given a map of traffic that says how many passengers travel from which station to which station. Compute the loss of the city when passengers swap their cards so that this loss is as large as possible. The loss is the total fare when nobody swaps a card, minus the smallest total fare that swapping can produce.

The first line of the input contains the number of test cases $T$. The first line of each test case contains the number of stations $N$ and the number $M$ of origin and endpoint pairs. Stations are numbered 1 to $N$. Each of the next $M$ lines contains three integers $o_i$, $e_i$ and $p_i$, meaning that $p_i$ passengers enter at station $o_i$ and leave at station $e_i$.

Limits:

• $1 \le T \le 20$
• $2 \le N \le 10^9$
• $1 \le M \le 1000$
• $1 \le o_i < e_i \le N$
• $1 \le p_i \le 10^9$

For each test case, print one line in the format Case #x: y, where $x$ is the test case number starting from 1, and $y$ is the loss of the city caused by card swapping, modulo 1000002013.

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