C :: Come to death

Time Limit: 10 Seconds    Memory Limit: 32768 KB

شاهزاده آرتاس در مبارزه با نامرده‌ها، متوجه شد آن‌ها به فرمان‌دهی کلتوزاد به شهر‌ها حمله می‌کنند و آن‌ها را آلوده می‌کنند، پس از آلوده‌شدن شهر‌ها تمام اعضای آن شهر به نامرده تبدیل می‌شوند. در ابتدا کلتوزاد در یک شهر مستقر است و می‌خواهد به شهر‌های دیگر سفر کند. هر شهر، تعدادی شهروند دارد. در صورتی که کلتوزاد به شهر i برود به اندازه‌ی p*di به نیروی نامرده‌ها افزوده می‌شود که p یک عدد ثابت و di تعداد شهروندان شهر i است. شهر‌ها به وسیله‌ی تعدادی جاده به هم متصل هستند و کلتوزاد برای سفر به شهر‌ها باید از این جاده‌ها بگذرد، برای گذر از جاده‌ی j باید به اندازه‌ی cj نیرو مصرف کند. هر شهر یک نمایندگی از کرین‌تور دارد که در صورتی که به آن‌ها اطلاع داده‌شود اجازه نمی‌دهند کسی به شهر وارد یا از آن خارج شود. برای اطلاع‌رسانی شهر‌ها، یک جاده انتخاب می‌شود(مثل j) و هزینه‌ی 10*cj به ۲ شهر منتهی به‌ آن، پرداخت می‌شود. عوارض (Cj) هیچ دو‌ جاده‌ای یکسان نیست.

شاهزاده آرتاس پس از این که متوجه نقشه‌ی کلتوزاد شد تصمیم گرفت جلوی او را بگیرد. به همین خاطر می‌خواهد به تمام شهر‌ها اطلاع‌رسانی کند. با توجه به این که برای اطلاع رسانی همان‌طور که در بالا گفته‌شد باید یک جاده انتخاب شود و هزینه‌ی آن پرداخت شود، آرتاس می‌خواهد کم‌ترین هزینه را بدهد و تمام‌ شهر‌ها نیز مطلع شوند. آرتاس هر صبح فقط می‌تواند یک جاده را انتخاب کند.

کلتوزاد به وسیله‌ی جاسوسان خود متوجه استراتژی آرتاس شد. او می‌خواهد به شهرهایی سفر کند و بیشترین سود را بکند هم‌چنین به هیچ شهری دو بار نرود تا به شهری برسد که نتواند به شهر دیگری برود (شهر‌های همسایه یا قبلا دیده‌ شده‌ا ست یا توسط آرتاس بسته شده‌است). کلتوزاد برای این که با آرتاس مواجه نشود، در شب سفر می‌کند. در اولین گام، کلتوزاد سفر می‌کند سپس آرتاس یک جاده را انتخاب می‌کند.

برنامه‌ای بنویسید تا با توجه به نکات گفته‌شده، مشخص کند کلتوزاد باید به ترتیب به چه شهر‌هایی برود تا بیش‌ترین نیرو را به دست آورد.

Input

در خط اول می‌آید که تعداد مورد‌هایی است که برنامه‌ی شما باید پاسخ دهد، درخط اول هر مورد‌ و و می‌آید که به ترتیب بیان‌گر تعداد شهر‌ها، تعداد جاده‌ها و هزینه‌ی ثابت سود هر شهر است. در خط بعد n عدد می‌آید که عدد i ام بیان‌گر di < 1000 برای شهر i ام است. در m خط بعدی، ۳ عدد i و j و c می‌آید که به این معنی است که شهر i و j به وسیله‌ی جاده‌ای با هزینه‌ی c به هم متصل‌اند. کلتوزاد از شهر شماره‌ی ۱ شروع به سفر می‌کند.

Output

برای هر مورد بیش‌ترین نیرویی که کلتوزاد می‌تواند به‌دست آورد را چاپ کنید.

Sample Input

3
8 10 20
0 1 1 1 1 1 1 1
1 5 3
1 2 4
2 3 5
1 3 7
3 4 8
4 5 9
4 6 6
5 6 11
6 7 10
7 8 12
8 10 2
0 25 10 10 10 10 10 10
1 5 3
1 2 4
2 3 5
1 3 7
3 4 8
4 5 9
4 6 6
5 6 11
6 7 10
7 8 12
8 10 10
0 10 10 10 999 10 10 10
1 5 3
1 2 4
2 3 5
1 3 7
3 4 8
4 5 9
4 6 6
5 6 11
6 7 10
7 8 12

Sample Output

57
87
9987

Submit