28713번 - Vjeverice 서브태스크다국어

문제

Živopisan Lund, gradić na jugu Švedske, krasi predivan park Botaniska Trädgården, a u njemu stanuju - vjeverice!

U parku je $n$ stabala, a vjeverice između $m$ parova stabala imaju označen puteljak. Svake godine ih dočeka isti problem: dođe jesen, lišće počne padati, i zatrpa im puteljke. Tada vjeverica moraju ponovno kamenčićima označavati sve puteljke. Već su to toliko puta ponovile da za svaki puteljak znaju koliko im je kamenčića potrebno da ga ponovo označe, za $i$-ti puteljak, koji spaja $a_i$-to stablo i $b_i$-stablo, potrebno im je $c_i$ kamenčića.

Za ovu godinu osmislile su novi plan: odlučile su ne označiti sve puteljke, nego samo njih $n - 1$. Učiniti će to na način da su sva stabla povezana, tj. između svakog para stabala postoji uzastopan niz označenih puteljaka koji od jednog stabla vodi do drugog. Dodatno, puteljke će odabrati na način da ukupan broj kamenčića na puteljcima bude najmanji moguć.

Koliko kamenčića će im biti potrebno?

Taman kad su se bacile na izračun potrebnih kamenčića, javilo se $q$ vjeverica, $i$-ta od njih izrazila je svoju sumnju u broj kamenčića potrebnih za označavanje puteljaka:

Za označiti $x_i$-ti puteljak potrebno nam je $d_i$ kamenčića, a ne $c_i$!.

Koliko im je ukupno kamenčića potrebno za označavanje puteljaka po novom planu ako je izjava $i$-te vjeverica istinita, a izjave ostalih vjeverica lažno?

입력

U prvom retku su prirodni brojevi $n$ i $m$ (2ドル ≤ n ≤ 100,000円,ドル 1ドル ≤ m ≤ \min(200,000,円 \frac{n \cdot (n-1)}{2})$), broj stabala u parku i broj puteljaka između njih.

Slijedi $m$ redaka po tri prirodna broja $a_i,ドル $b_i$ i $c_i$ (1ドル ≤ a_i , b_i ≤ n,ドル $a_i \ne b_i,ドル 1ドル ≤ c_i ≤ 1,000円$), a koji označavaju da $i$-ti puteljak spaja stabla $a_i$ i $b_i,ドル a za njegovo označavanje potrebno je $c_i$ kamenčića.

U sljedećem retku je cijeli broj $q$ (1ドル ≤ q ≤ 100,000円$), broj nesigurnih vjeverica.

Slijedi $q$ redaka po dva prirodna broja $x_i$ i $d_i$ (1ドル ≤ x_i ≤ m,ドル 1ドル ≤ d_i ≤ 1,000円$), brojevi u izjavi $i$-te vjeverice ($x_i$ je redni broj puteljka u ulaznim podacima).

Ulazni podaci će biti takvi da će sva stabla biti povezana, a između svakog para stabala biti će najviše jedan puteljak.

출력

Ispišite $n$ redaka. U prvom retku ispišite traženi broj kamenčića prije izjava. U $i + 1$-tom retku ispišite traženi broj kada je jedino izjava $i$-te vjeverice istinita.

제한

서브태스크

힌트

Pojašnjenje drugog probnog primjera: Na ilustracijama su prikazani puteljci i potreban broj kamenčića po puteljku. Puteljci označeni punom crtom su puteljci koji će vjeverice označiti kamenčićima, a oni isprekidanom crtom su puteljci koje neće označiti kamenčićima. Crvenom bojom označen je puteljak u sumnji $i$-te vjeverice. Ilustracije su poredane kao upiti u primjeru.