+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۱۶۰ مگابایت ---------- یک گراف $n$ راسی همبند با $m$ یال وزن‌دار داریم. در راس $i$ ام $p_i$ نفر زندگی میکنند. وزن های این $m$ یال متفاوت است. تیزی $k$ یال دیگر بجز این $m$ یال دارد که وزن های آنها هنوز تعیین نشده است. او میتواند وزن این یال ها را هر عددی بگذارد. (حتی برابر با وزن یکی از $m$ یال ابتدایی) تیزی پس از تعیین وزن یال های جدیدش، باید یک MST از گراف انتخاب کند. اگر چند حالت برای انتخاب این MST وجود دارد او میتواند هرکدام از حالت ها را بردارد. سپس هر نفر در هر یک از راس ها به سمت راس ۱ حرکت میکند. هر نفر برای عبور از یک یال باید به اندازه وزن آن یال به تیزی پول بدهد. طبعن افراد فقط میتوانند از یال های MST انتخاب شده ی تیزی استفاده کنند! تیزی میخواهد ماکسیمم پول را کسب کند. به او بگویید این مقدار چقدر است اگر او وزن $k$ یال را به بهترین حالت تعیین کند. # ورودی در خط اول ورودی $n$ و $m$ و $k$ به شما داده میشود که به ترتیب تعداد راس های گراف و تعداد یال های ابتدایی و تعداد یال هایی است که تیزی وزن آنها را تعیین خواهد کرد. در هر یک از $m$ خط بعدی ۳ عدد $a$ و $b$ و $c$ به شما داده میشود که نشان دهنده وجود یالی بین $a$ و $b$ با وزن $c$ است. تضمین میشود همه $c$ ها متفاوتند. در هر یک از $k$ خط بعدی ۲ عدد $a$ و $b$ به شما داده میشود که نشان‌دهنده یک یال بین $a$ و $b$ است که وزن این یال را تیزی تعیین خواهد کرد. در خط آخر $n$ عدد $p_1,p_2,...,p_n$ به شما داده میشود. $$1\leq n \leq 10^5$$ $$1\leq m \leq 3*10^5$$ $$1\leq k \leq 20$$ $$1\leq p_i,c \leq 10^6$$ # خروجی در تنها خط خروجی ماکسیمم پولی که تیزی میتواند کسب کند را بدهید. # مثال ## ورودی نمونه ۱ ``` 5 5 1 3 5 2 1 2 3 2 3 5 2 4 4 4 3 6 1 3 10 20 30 40 50 ``` ## خروجی نمونه ۱ ``` 400 ``` تیزی میتواند وزن یال بین ۱ و ۳ را ۵ قرار دهد و ۴۰۰ تا سود کند.