V Slovakistane sa blížia voľby a tak aby sa mal terajší minister dopravy čím oháňať, rozhodol sa postaviť niekoľko nových ciest. V Slovakistane je $n$ dôležitých miest, pričom medzi každými dvoma mestami leží obojsmerná cesta kladnej dĺžky. Minister dopravy navrhol plán výstavby $q$ ciest, ktoré sa uskutočnia jedna za druhou. Obyvatelia Slovakistanu sú však podozrievaví, že nové cesty boli navrhnuté bez rozmyslu a pri cestovaní po krajine im až tak nepomôžu. Chceli by teda vedieť ako veľmi každá cesta pomôže doprave po krajine - ako merítko si zvolili súčet dĺžok ciest medzi všetkými (neusporiadanými) dvojicami miest. Keďže však Slovakistanci nie sú šikovní programátori, obrátili sa na vás.
Mestá Slovakistanu s cestami medzi nimi tvoria neorientovaný ováhovaný graf. Vzdialenosť medzi dvoma mestami je najkratšia vzdialenosť ktorá je dosiahnuteľná použitím postavených ciest na prepravu z jedného mesta do druhého; v tejto úlohe nás teda bude po každej novopostavenej ceste zaujímať súčet týchto dĺžok pre všetky neusporiadané dvojice miest.
V prvom riadku je číslo $2 \leq n \leq 300$ - počet miest v Slovakistane.
Nasleduje $n$ riadkov po $n$ číslach. Číslo v $i$-tom riadku a $j$-tom stĺpci označuje dĺžku cesty medzi mestom $i$ a mestom $j$, označíme si ho $d_{ij}$. Platí $d_{ij} = d_{ji}$, $d_{ii} = 0$, a $1 \leq d_{ij} \leq 1000$ pre $i \neq j$.
Potom nasleduje číslo $1 \leq q \leq 300$ - počet plánovaných ciest.
Nasleduje $q$ riadkov, každé popisujúce jednu cestu v tom poradí, v akom budú postavené.
Každá nová cesta je popísaná trojicou čísel $a b c$, $1 \leq a,b \leq n$, $1 \leq c \leq 1000$ - mestá, ktoré bude nová obojsmerná cesta spájať a jej dĺžka. Staršie cesty ktoré medzi $a$ a $b$ existovali ostávajú postavené.
Vypíšte $q$ riadkov s jedným číslom $s_i$ - súčet vzdialeností medzi všetkými neusporiadanými dvojicami miest po postavení nových ciest $1,...,i$.
3
0 4 9
4 0 4
9 4 0
2
1 2 1
2 3 1
10
4