B. Задолженности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Представьте себе, что в вашей дружеской компании три человека: A, B и С. При этом A должен B 20 рублей, а B должен C 20 рублей. Общая сумма задолженностей равна 40 рублей. Можно заметить, что задолженности в этом случае устроены не самым оптимальным образом. Перераспределим задолженности следующим образом: пусть A должен C 20 рублей, а B ничего никому не должен. Смысл задолженностей не изменился, а сумма всех задолженностей стала равна 20 рублей.

Эта задача обобщает описанный пример. Представьте, что в вашей дружеской компании n человек, и известны задолженности между людьми. Оптимизируйте заданные задолженности, не меняя их смысла. Другими словами в итоге для каждого человека разность того, сколько он должен отдать, и сколько он должен получить, должна сохраниться. Выведите минимальную сумму всех задолженностей в оптимальном распределении задолженностей. Посмотрите пояснение тестовых примеров для лучшего понимания задачи.

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n ≤ 100; 0 ≤ m ≤ 104). В следующих m строках заданы задолженности. В i-ой строке записаны три целых числа ai, bi, ci (1 ≤ ai, bi ≤ nai ≠ bi; 1 ≤ ci ≤ 100), которые означают, что человек ai должен человеку bi ci рублей.

Считайте, что люди пронумерованы от 1 до n целыми числами.

Гарантируется, что одна и та же пара людей встречается во входных данных не более одного раза. Во входных данных не встречается одновременно пара людей (x, y) и пара людей (y, x).

Выходные данные

Выведите единственное целое число — минимальную сумму задолженностей в оптимальном распределении.

Примеры
Входные данные
5 3
1 2 10
2 3 1
2 4 1
Выходные данные
10
Входные данные
3 0
Выходные данные
0
Входные данные
4 3
1 2 1
2 3 1
3 1 1
Выходные данные
0
Примечание

В первом примере можно считать, что человек с номером 1 должен человеку с номером 2 8 рублей, человеку с номером 3 1 рубль и человеку с номером 4 1 рубль. Больше никто никому не должен. В итоге суммарная задолженность равна 10.

Во втором примере нет никаких задолженностей.

В третьем примере можно аннулировать все задолженности.