Little H has loved computers since he was a child, and after entering middle school, he became even more obsessed with computer programming. After years of unremitting efforts, Little H was fortunately selected for the informatics competition provincial team and is about to go to Zhengzhou, Henan, to participate in the 22nd National Olympiad in Informatics (NOI2005), a place he has dreamed of visiting.

Little H's good friends, Little Y and Little Z, were genuinely happy for him when they heard the news. They decided to host a party, inviting Little H and all his friends to celebrate for him.

After several days of investigation, Little Y and Little Z listed all of Little H's friends, totaling $N$ people (for convenience, we number them as integers from $1$ to $N$). However, there are too many people on the list, and many of them are not known to Little Y and Little Z. How can they organize them all to attend the party?

Little Y and Little Z hope to design a contact network for Little H's $N$ friends so that if one person learns the latest news about the party, everyone else can receive the news directly or indirectly. At the same time, to ensure that the message delivery is simple, efficient, and most importantly, confidential (to give Little H a surprise, the news of the party must absolutely not be known to him during the preparation stage), Little Y and Little Z decided to let as few friends as possible contact each other directly: to ensure that all $N$ friends can be connected directly or indirectly, it is only necessary to have $(N-1)$ pairs of friends in direct contact.

Figure 1

Obviously, not all friends on the list know each other, and even for two people who know each other, the degree of familiarity between them varies. Therefore, Little Y and Little Z listed a relationship table between friends based on the investigation results, indicating which people can be in direct contact. For each pair of friends who can be in direct contact, Little Y and Little Z also marked the "happiness level" of their contact. For example, the relationship between 3 and 4 is very good, so the happiness level of their contact is marked as 10; while 1 and 3 are just ordinary friends, so their happiness level is lower. Figure 1 above shows a contact table for $N=5$, where points represent friends on the list, edges represent that two friends can be in direct contact, and the numbers on the edges are the happiness levels of their contact.

Little Y and Little Z hope that everyone will enjoy this party, so they decided to maximize the happiness level of the contact network: the happiness level of the contact network is the sum of the happiness levels of every pair of directly connected people. For example, in Figure 1, the bold edges represent a network with the maximum happiness level, and its happiness level is $5+6+10+5=26$.

However, if someone is allowed to be in direct contact with many people, this will inevitably add a great burden to them. Therefore, Little Y and Little Z also set a maximum number of direct contacts $k_i$ for each person, indicating that at most $k_i$ people can be in direct contact with $i$ in the contact network.

Still using the example in Figure 1, if we add the constraints $k_i = 1, 1, 4, 2, 2$ for each point from 1 to 5 respectively, the above scheme will not meet the requirements. At this time, the optimal scheme is shown in Figure 2, and its happiness level is $3+6+10+5 = 24$.

Figure 2

Can you help Little Y and Little Z find a contact network with the maximum possible happiness level while satisfying the constraints?

Input

The input files party1.in to party10.in are already placed in the user directory.

The first line of each input file contains two integers $N$ and $M$. $N$ represents the total number of Little H's friends, and $M$ represents the number of pairs of friends that Little Y and Little Z listed as being able to be in direct contact.

The second line of the input file contains $N$ integers in the range $[1, N-1]$, describing $k_1, k_2, \dots, k_N$ in order. Adjacent numbers are separated by a space.

The following $M$ lines each describe a pair of friends who can be in direct contact, in the format $u_i \ v_i \ c_i$. This indicates that $u_i$ and $v_i$ can be in direct contact, and their contact happiness level is $c_i$.

In addition, at the end of all this data, there is a separate line containing a real number $d$ in the range $(0, 1]$ as a scoring coefficient. Your program does not need to pay attention to this parameter, but you can refer to this parameter to design different algorithms. For the explanation of $d$, please refer to the scoring method below.

Output

This is a submission-style problem; you need to provide ten output files from party1.out to party10.out.

The first line of each file is an integer representing the maximum happiness level you found.

The following $(N-1)$ lines describe this network. Each line contains a number $e_i$, indicating that in the network, the pair of friends described in the $(e_i + 2)$-th line of the input file are in direct contact.

Examples

Input 1

5 6 
1 1 4 2 2 
1 2 5 
1 3 3 
2 3 6 
2 5 3 
3 4 10 
4 5 5 
0.00001

Output 1

24 
2 
3 
5 
6

Note

See the example in the task description.

Subtasks

This problem has partial points. For each test case:

If your output scheme is invalid, i.e., $e_i$ does not meet the range, or $e_i$ has duplicates, or the network is not connected, etc., the test case gets 0 points.

If your output scheme is inconsistent with the happiness level in the first line of the output file, the test case gets 0 points.

Otherwise, the score for this test case is calculated as follows: Let $$a = (1 - d) \times \text{our\_ans}$$ $$b = (1 + d \times 0.5) \times \text{our\_ans}$$

If your result is less than $a$, the test case gets 0 points; If your result is greater than $b$, the test case gets 15 points; Otherwise, your score is: $$\left\lfloor \frac{\text{your\_ans} - a}{\text{our\_ans} - a} \times 10 \right\rfloor$$

Where $d$ is the scoring coefficient (the real number in the last line of the input data), $\text{our\_ans}$ is the reference solution we provide, and $\text{your\_ans}$ is your answer.

Interaction

We provide a tool called party_check to test your output files. The method to use this tool is to enter the following in the console:

./party_check <test case number X>

After you call this program, party_check will give the test results based on the input file partyX.in and your output file partyX.out, which include:

• Error: Not connected: The contact network output by your program is not connected;
• Error: Edge xxx is duplicated: The xxx-th edge was output twice;
• Error: Edge in Line xxx is out of range: The edge index output by your program on line xxx is not in the range $[1, M]$;
• Error: Degree of Friend xxx is out of range: In the contact network, the number of people in direct contact with friend xxx exceeds the limit;
• Error: Scheme & happiness mismatch: The scheme is inconsistent with the happiness level on the first line;
• Test program exited illegally: Other situations;
• Correct! Happiness = xxx: Output is correct.