pedrumuriminime

Se dă un graf neorientat cu $n$ noduri și cu costuri asociate muchiilor. Se pun mai multe întrebări de forma $(i, j, k)$ cu semnificația: Se află nodul $k$ pe un drum de cost minim de la nodul $i$ la nodul $j$?

Date de intrare

Fișierul de intrare pedrumuriminime.in conține pe prima linie două numere naturale $n$ și $m$ reprezentând numărul de noduri și numărul de muchii ale grafului dat. Pe următoarele $m$ linii se află câte $3$ numere naturale, separate prin câte un spațiu, $x \ y \ c$ cu semnificația că există muchie bidirecționale de la $x$ la $y$ și care are costul $c$.
Pe linia următoare este un număr $q$, reprezentând numărul de întrebări.
Pe următoatele $q$ linii se află câte $3$ numere $i \ j \ k$, cu semnificația de mai sus.

Date de ieșire

Fișierul de ieșire pedrumuriminime.out va conține $q$ valori de $0$ și $1$, neseparate prin spații, reprezentând răspunsurile la întrebările puse ($1$ reprezintă răspuns afirmativ).

Restricții și precizări

• $1 \leq n \leq 300$
• $1 \leq m \leq$ numărul maxim posibil de muchii ale grafului
• $1 \leq q \leq 100 \ 000$
• Muchiile date sunt distincte
• $x \not = y$ în toate datele de intrare
• Costurile muchiilor sunt numere naturale nenule cel mult egale cu $1 \ 000 \ 000$
• În cadrul fiecărui triplet $i, j, k$ sunt diferite între ele
• Costul unui drum este definit ca suma costurilor muchiilor de pe acel drum

Exemplu

pedrumuriminime.in

4 4
1 2 3
1 3 1
2 3 1
1 4 5
2
1 2 3
1 2 4

pedrumuriminime.out

10