Operatii 3

Romică a primit de ziua lui un șir $w$ de $n$ numere naturale. Uraaa!

Romică, displăcând structurile prăfuite de date cum ar fi șirurile de numere întregi, a decis să facă ceva mai interesant, să considere fiecare index de la $1$ la $n$ ca un nod într-un graf și să înceapă să tragă muchii între ele. Doar că Romică vrea să se provoace un pic, așa că nu va trage muchii în orice mod obișnuit.

Întâi, își propune să creeze o listă de $m$ triplete de numere $a_i$, $b_i$, $s_i$. Apoi, va efectua următoarea operație (până când nu mai este posibil).

1. Întâi, determină un $i$ minim astfel încât $a_i$ și $b_i$ se află în componente diferite, și în plus, că suma tuturor nodurilor $w$-urilor care se află în aceeași componentă cu $a_i$ sau $b_i$ este cel puțin $s_i$.
2. Apoi, trage o muchie între nodurile $a_i$ și $b_i$, și scrie numărul $i$ în capătul unei liste.

Desigur, dacă Romică încă e la vârsta în care se poate bucura de un șir de n numere naturale, înseamnă că probabil e încă prea tânăr ca să poată să rezolve o asemenea problemă. Ajutați-l, vă rog eu mult de tot, să determine lista cu ordinea în care se vor efectua operațiile!

Date de intrare

Prima linie a datelor de intrare conține doi întregi, $n$ și $m$ ($1 \leq n, m \leq 3 \cdot 10^5$): numărul de noduri și numărul de tuplete pe care le are în plan Romică.

A doua linie conține $n$ numere, anume $w_1, w_2, \ldots, w_n$, șirul de numere făcut cadou lui Romică ($1 \leq w_i \leq 10^6$).

Următoarele $m$ linii conțin descrierea tupletelor. Fiecare din acestea conțin trei numere întregi, $a_i$, $b_i$, $s_i$ ($1 \leq a_i, b_i \leq n$, $1 \leq s_i \leq 10^6$).

Date de ieșire

Pe prima linie a fișierului de ieșire se va afla întâi numărul de operații pe care le-ar efectua Romică. Apoi, se vor afla atâtea numere câte sunt operații, reprezentând lista cerută în cerință.

Restricții și precizări

• $1 \le n, m \le 3 \cdot 10^5$;
• $1 \le w_i, s_i \le 10^6$;
• $1 \le a_i, b_i, \le n$

Exemplul 1

stdin

8 14
17 2 3 1 2 2 3 4
2 7 6
1 6 19
3 1 21
7 2 7
1 3 22
2 3 34
7 5 4
4 8 5
3 8 27
7 8 34
8 4 4
7 5 5
3 8 27
1 6 18

stdout

7
2 3 7 1 8 9 6

Exemplul 2

stdin

14 13
3 2 3 1 3 1 2 15 1 2 2 4 1 3
1 8 23
5 10 4
11 2 39
13 8 16
9 8 42
7 9 2
5 6 6
13 2 20
3 5 33
14 4 4
1 4 37
3 12 28
3 2 4

stdout

13
2 4 6 7 10 13 8 1 12 9 11 3 5