+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --------------------------------- محمدسام تصمیم گرفته است یک گراف را به روشی خاص بسازد. او فهرستی از یال‌های پیشنهادی در اختیار دارد، اما تنها زمانی می‌تواند یک یال را به گراف اضافه کند که مجموع وزن دو مؤلفه‌ای که دو سر آن یال در آن‌ها قرار دارند، به اندازه‌ی کافی بزرگ باشد. هر بار که یالی اضافه می‌کند، شماره‌ی آن را در دفترچه‌ی خود یادداشت می‌کند؛ اما پس از پایان کار، دفترچه‌اش گم می‌شود! حالا شما باید این شماره‌ها را بازیابی کنید. در ابتدا یک گراف بدون یال با $n$ رأس داریم. به هر رأس یک وزن (عدد صحیح نامنفی) اختصاص داده شده است. وزن راس $i$ برابر با $w_i$ است. همچنین $m$ سه‌تایی به صورت $(a_i, b_i, s_i)$ داده شده است که کاندید‌های یال‌های گراف است. $a_i$ و $b_i$ دو رأس و $s_i$ یک عدد صحیح نامنفی است. سپس محمدسام فرایند زیر را بارها تکرار می‌کند: + اگر اندیس $i$ ای وجود داشت که رأس‌های $a_i$ و $b_i$ در دو مؤلفه‌ی همبند متفاوت قرار داشته باشند و مجموع وزن رأس‌های دو مؤلفه‌ی آن‌ها حداقل برابر با $s_i$ باشد، **کوچکترین $i$ با این ویژگی** انتخاب می‌شود، سپس محمدسام $i$ را در دفترچه‌ خود یادداشت می‌کند و در نهایت یالی بین $a_i$ و $b_i$ به گراف اضافه‌ می‌کند. + اگر چنین $i$ ای وجود نداشت، فرآیند خاتمه می‌یابد. شما باید شماره‌هایی را که در پایان در دفترچه ثبت شده‌اند، به همان ترتیب بازیابی کنید. # ورودی در خط اول دو عدد صحیح $n$ و $m$ داده می شود که به‌ترتیب تعداد رأس‌های گراف و تعداد یال‌های مدنظر است. در خط دوم $n$ عدد صحیح $w_1, w_2, \ldots, w_n$ داده می‌شود که وزن رأس‌ها را مشخص می‌کنند. در $m$ خط بعد، هر خط شامل سه عدد صحیح $a_i$، $b_i$ و $s_i$ است که یکی از سه‌تایی‌های داده‌شده را توصیف می‌کند. $$1 \leq n, m \leq 2 \times 10^5$$ $$1 \leq a_i, b_i \leq n \ \ (a_i \ne b_i)$$ $$0 \leq w_i, s_i \leq 10^6$$ # خروجی در خط اول، تعداد شماره‌هایی را که در دفترچه نوشته شده‌اند چاپ کنید. در خط دوم، این شماره‌ها را **به همان ترتیبی که نوشته شده‌اند** چاپ کنید. # مثال ## ورودی نمونه ۱ ```text 5 5 1 4 3 4 0 4 5 5 3 1 1 2 5 2 4 3 1 4 1 4 ``` ## خروجی نمونه ۱ ```text 4 2 3 1 4 ``` ## ورودی نمونه ۲ ```text 3 5 3 2 2 1 2 6 1 2 6 1 2 3 1 2 6 2 3 6 ``` ## خروجی نمونه ۲ ```text 2 3 5 ```