The Kingdom of Byteland decided to develop a large computer network of servers oering various
services.

<P>
The network is built of n servers connected by bidirectional wires. Two servers can be directly
connected by at most one wire. Each server can be directly connected to at most 10 other servers
and every two servers are connected by some path in the network. Each wire has a fixed positive data
transmission time measured in milliseconds. The distance (in milliseconds) <!-- MATH
 $\delta(V, W)$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
 SRC="2666img1.png"
 ALT="$ \delta$">(<I>V</I>, <I>W</I>)</SPAN> between two servers
<SPAN CLASS="MATH"><I>V</I></SPAN> and <SPAN CLASS="MATH"><I>W</I></SPAN> is defined as the length of the shortest (according to transmission time) path connecting <SPAN CLASS="MATH"><I>V</I></SPAN>
and <SPAN CLASS="MATH"><I>W</I></SPAN> in the network. For convenience we let <!-- MATH
 $\delta(V, V) = 0$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
 SRC="2666img1.png"
 ALT="$ \delta$">(<I>V</I>, <I>V</I>) = 0</SPAN> for all <SPAN CLASS="MATH"><I>V</I></SPAN>.

<P>
Some servers oer more services than others. Therefore each server <SPAN CLASS="MATH"><I>V</I></SPAN> is marked with a natural
number <SPAN CLASS="MATH"><I>r</I>(<I>V</I>)</SPAN>, called a rank. The bigger the rank the more powerful a server is.

<P>
At each server, data about nearby servers should be stored. However, not all servers are interesting.
The data about distant servers with low ranks do not have to be stored. More specifically, a server <SPAN CLASS="MATH"><I>W</I></SPAN> is
interesting for a server <SPAN CLASS="MATH"><I>V</I></SPAN> if for every server <SPAN CLASS="MATH"><I>U</I></SPAN> such that <!-- MATH
 $\delta(V, U) \le \delta(V, W)$
 -->
<SPAN CLASS="MATH"><IMG
 WIDTH="13" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
 SRC="2666img1.png"
 ALT="$ \delta$">(<I>V</I>, <I>U</I>)<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><IMG
 WIDTH="13" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
 SRC="2666img1.png"
 ALT="$ \delta$">(<I>V</I>, <I>W</I>)</SPAN> we have <!-- MATH
 $r(U) \le r(W)$
 -->
<SPAN CLASS="MATH"><I>r</I>(<I>U</I>)<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><I>r</I>(<I>W</I>)</SPAN>.

<P>
For example, all servers of the maximal rank are interesting for all servers. If a server <SPAN CLASS="MATH"><I>V</I></SPAN> has the
maximal rank, then exactly the servers of the maximal rank are interesting for <SPAN CLASS="MATH"><I>V</I></SPAN>. Let <SPAN CLASS="MATH"><I>B</I>(<I>V</I>)</SPAN> denote the
set of servers interesting for a server <SPAN CLASS="MATH"><I>V</I></SPAN>.

<P>
We want to compute the total amount of data about servers that need to be stored in the network
being the total sum of sizes of all sets <SPAN CLASS="MATH"><I>B</I>(<I>V</I>)</SPAN>. The Kingdom of Byteland wanted the data to be quite
small so it built the network in such a way that this sum does not exceed <SPAN CLASS="MATH">30<I>n</I></SPAN>.

<P>

<P>
<BR>
Write a program that:

<UL>
<LI>reads the description of a server network from the standard input,
</LI>
<LI>computes the total amount of data about servers that need to be stored in the network,
</LI>
<LI>writes the result to the standard output.
</LI>
</UL> 

<P>

<H2><FONT size=4 COLOR=#ff0000><A NAME="SECTION0001001000000000000000">
Input</A>&nbsp;</FONT>
</H2>
The first line of the input cointains an integer indicating the number of datasets. It's followed by a blank line.
The first line of each dataset contains two natural numbers <SPAN CLASS="MATH"><I>n</I></SPAN>, <SPAN CLASS="MATH"><I>m</I></SPAN>, where <SPAN CLASS="MATH"><I>n</I></SPAN> is the number of servers in the network
(<!-- MATH
 $1 \le n \le 30 000$
 -->
<SPAN CLASS="MATH">1<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><I>n</I><IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$">30000</SPAN>) and <SPAN CLASS="MATH"><I>m</I></SPAN> is the number of wires (<!-- MATH
 $1 \le m \le 5n$
 -->
<SPAN CLASS="MATH">1<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><I>m</I><IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$">5<I>n</I></SPAN>). The numbers are separated by single
space.

<P>
The ranks of the servers are given in the next <SPAN CLASS="MATH"><I>n</I></SPAN> lines. Line <SPAN CLASS="MATH"><I>i</I></SPAN> contains one integer <SPAN CLASS="MATH"><I>r</I>(<I>i</I>)</SPAN> (<!-- MATH
 $1 \le r(i) \le 10$
 -->
<SPAN CLASS="MATH">1<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><I>r</I>(<I>i</I>)<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$">10</SPAN>) - the rank of the <SPAN CLASS="MATH"><I>i</I></SPAN>-th server.

<P>
The wires are described in the next <SPAN CLASS="MATH"><I>m</I></SPAN> lines. Each wire is described by three numbers <SPAN CLASS="MATH"><I>a</I></SPAN>, <SPAN CLASS="MATH"><I>b</I></SPAN>, <SPAN CLASS="MATH"><I>t</I></SPAN> (<!-- MATH
 $1 \le t \le
1000$
 -->
<SPAN CLASS="MATH">1<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><I>t</I><IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$">1000</SPAN>, <!-- MATH
 $1 \le a, b \le n$
 -->
<SPAN CLASS="MATH">1<IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><I>a</I>, <I>b</I><IMG
 WIDTH="18" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img2.png"
 ALT="$ \le$"><I>n</I></SPAN>, <SPAN CLASS="MATH"><I>a</I><IMG
 WIDTH="18" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
 SRC="2666img3.png"
 ALT="$ \ne$"><I>b</I></SPAN>), where <SPAN CLASS="MATH"><I>a</I></SPAN> and <SPAN CLASS="MATH"><I>b</I></SPAN> are numbers of the servers connected by the wire and <SPAN CLASS="MATH"><I>t</I></SPAN> is the
transmission time of the wire in milliseconds.

<P>

<H2><FONT size=4 COLOR=#ff0000><A NAME="SECTION0001002000000000000000">
Output</A>&nbsp;</FONT>
</H2>
The output for each dataset consists of a single integer equal to the total amount of data about servers that need to be stored in the network.
Print a blank line between datasets.
<P>

<H2><FONT size=4 COLOR=#ff0000><A NAME="SECTION0001003000000000000000">
Sample Input</A>&nbsp;</FONT>
</H2>
<PRE>
1

4 3
2
3
1
1
1 4 30
2 3 20
3 4 20
</PRE>

<P>

<H2><FONT size=4 COLOR=#ff0000><A NAME="SECTION0001004000000000000000">
Sample Output</A>&nbsp;</FONT>
</H2>
<PRE>
9
</PRE>

<P>

<P><P>
<BR>

<B>Note:</B> Because <!-- MATH
 $B(1) = \{1, 2\}$
 -->
<SPAN CLASS="MATH"><I>B</I>(1) = {1, 2}</SPAN>, <!-- MATH
 $B(2) = \{2\}$
 -->
<SPAN CLASS="MATH"><I>B</I>(2) = {2}</SPAN>, <!-- MATH
 $B(3) = \{2, 3\}$
 -->
<SPAN CLASS="MATH"><I>B</I>(3) = {2, 3}</SPAN>, <!-- MATH
 $B(4) = \{1, 2, 3, 4\}$
 -->
<SPAN CLASS="MATH"><I>B</I>(4) = {1, 2, 3, 4}</SPAN>.

<P>