Существует дилемма, известная как проблема вагонетки. В ней вы управляете движущимся к переезду поездом. На переезде вы можете сменить текущее направление движения на альтернативное. По исходному направлению на пути поезда лежит пять человек, а по альтернативному — один. Кто-то так или иначе погибнет.
Рудольф столкнулся с этой проблемой в несколько большем масштабе. Существует разветвленная сеть железных дорог, состоящая из развилок, соединенных односторонними дорогами. Сеть ациклична, то есть поезд не может дважды оказаться на одной развилке. Поезд начинает с развилки номер $$$1$$$. На дорогах расположены люди.
Некоторые развилки являются управляемыми, то есть можно выбрать одну из двух дорог, и поезд может ехать только по указанной дороге. Управляемыми могут быть только те развилки, от которых идут ровно две дороги. Чтобы поменять направление управляемой развилки, нужно дернуть один из рычагов. При этом один рычаг может отвечать сразу за несколько развилок, то есть все развилки, управляемые одним рычагом, переключаются одновременно. Каждая развилка управляется только одним рычагом.
Перед поездкой Рудольф может переключить любые рычаги. Он хочет сделать это так, чтобы поезд доехал до любого тупика (развилки, из которой нет дорог), сбив как можно меньше людей. Помогите ему вычислить минимальное количество жертв.
Первая строка входных данных содержит два целых числа $$$N$$$, $$$M$$$ $$$(1 \le N \le 1000, N-1 \le M \le min(20000, \frac{N\cdot(N-1)}{2}))$$$ — количество развилок и количество дорог.
Следующие $$$M$$$ строк содержат по три целых числа $$$A$$$, $$$B$$$, $$$C$$$ $$$(1 \le A, B \le N, 1 \le C \le 1000)$$$ — описание дороги: номер развилки, в которой начинается дорога; номер развилки, в которой заканчивается дорога; количество людей на дороге.
Следующая строка содержит целое число $$$G$$$ $$$(0 \le G \le N)$$$ — количество управляемых развилок.
Следующие $$$G$$$ строк содержат по три целых числа $$$X$$$, $$$Y$$$, $$$Z$$$ $$$(1 \le X, Z \le N, 1 \le Y \le 10)$$$ — описание управляемой развилки: номер развилки; номер рычага, отвечающего за развилку; и номер развилки, в которую идет дорога, на которую изначально указывает данная развилка.
Выведите единственное целое число — минимальное количество людей, попавших под поезд.
8 10 1 2 4 1 3 6 2 4 3 2 5 2 4 6 2 3 7 10 3 8 12 3 8 8 7 5 6 3 6 13 2 1 1 3 2 1 5
9
5 5 1 2 15 1 3 5 3 4 8 3 5 7 2 5 2 2 1 2 2 3 4 5
12
