Imagine that there is a group of three friends: A, B and С. A owes B 20 rubles and B owes C 20 rubles. The total sum of the debts is 40 rubles. You can see that the debts are not organized in a very optimal manner. Let's rearrange them like that: assume that A owes C 20 rubles and B doesn't owe anything to anybody. The debts still mean the same but the total sum of the debts now equals 20 rubles.

This task is a generalisation of a described example. Imagine that your group of friends has n people and you know the debts between the people. Optimize the given debts without changing their meaning. In other words, finally for each friend the difference between the total money he should give and the total money he should take must be the same. Print the minimum sum of all debts in the optimal rearrangement of the debts. See the notes to the test samples to better understand the problem.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 100; 0 ≤ m ≤ 10^4). The next m lines contain the debts. The i-th line contains three integers a_{i}, b_{i}, c_{i} (1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}; 1 ≤ c_{i} ≤ 100), which mean that person a_{i} owes person b_{i} c_{i} rubles.

Assume that the people are numbered by integers from 1 to n.

It is guaranteed that the same pair of people occurs at most once in the input. The input doesn't simultaneously contain pair of people (x, y) and pair of people (y, x).


-----Output-----

Print a single integer — the minimum sum of debts in the optimal rearrangement.


-----Examples-----
Input
5 3
1 2 10
2 3 1
2 4 1

Output
10

Input
3 0

Output
0

Input
4 3
1 2 1
2 3 1
3 1 1

Output
0



-----Note-----

In the first sample, you can assume that person number 1 owes 8 rubles to person number 2, 1 ruble to person number 3 and 1 ruble to person number 4. He doesn't owe anybody else anything. In the end, the total debt equals 10.

In the second sample, there are no debts.

In the third sample, you can annul all the debts.

Difficulty: interview

Starter code:

Solutions:
data = input().split(" ")
n = int(data[0])
m = int(data[1])
debts = []
total = 0
for i in range(n):
	debts.append(0)
for i in range(m):
	data = input().split(" ")
	data = [int(x) for x in data]
	debts[data[0]-1] -= data[2]
	debts[data[1]-1] += data[2]

for i in range(len(debts)):
	if debts[i] < 0:
		total += (debts[i]*-1)

print(total)

def debt(n, r):
    for i in range(n):
        a, b, c = [int(i) for i in input().split()]
        r[a-1] -= c
        r[b-1] += c
    r = [abs(i) for i in r]
    return int(sum(r)/2)

def main():
    n, m = [int(i) for i in input().split()]
    r = [0 for i in range(n)]
    print(debt(m, r))

def __starting_point():
    main()
__starting_point()

n, m = map(int, input().split());
mas = [0] * (n + 1);
for i in range (m) :
    a, b, c = map(int, input().split());
    mas[b] += c;
    mas[a] -= c;

sum = 0;
for i in mas :
    sum += max (i, 0);
print (sum);

n, m = map(int, input().split());
mas = [0] * (n + 1);
for i in range (m) :
    a, b, c = map(int, input().split());
    mas[b] += c;
    mas[a] -= c;

sum = 0;
for i in mas :
    sum += max (i, -i);
print (int(sum / 2));

n, m = map(int, input().split())
p = [0] * (n + 1)
for i in range(m):
    a, b, d = map(int, input().split())
    p[a] += d
    p[b] -= d
print(sum(abs(i) for i in p) // 2)

n,m = list(map(int,input().split()))
xs = [0]*n
for _ in range(m):
    a,b,c = list(map(int,input().strip().split()))
    xs[a-1] -= c
    xs[b-1] += c
print(sum(x for x in xs if x>0))


n, k = map(int, input().split())
p = [0] * (n + 1)
for i in range(k):
    a, b, d = map(int, input().split())
    p[a] += d
    p[b] -= d
print(sum(map(abs, p)) // 2)

n,m = (map(int,input().split()))
s = [0] * n
for i in range(m):
    a,b,c = (map(int,input().split()))
    s[a-1] -= c
    s[b-1] += c
print(sum(s[i] for i in range(n) if s[i] > 0))

__author__ = 'asmn'
n, m = tuple(map(int, input().split()))
l = [0] * n
for i in range(m):
    a, b, c = tuple(map(int, input().split()))
    l[a - 1] += c
    l[b - 1] -= c

print(sum(abs(x) for x in l)//2)

n,m = map(int,input().split())
debts = [0]*n
credit = [0]*n
for cont in range(0,m):
    x,y,c = map(int, input().split())
    debts[x-1] += c
    credit[y-1] += c

total = [0]*n
for cont in range(0,n):
    total[cont] = debts[cont]-credit[cont]

ris = 0
for n in total:
    if n > 0:
        ris += n

print(ris)

n,m=list(map(int,input().split()))
d=[0]*n
for i in range(m):
    a,b,c=list(map(int,input().split()))
    d[a-1]-=c
    d[b-1]+=c
ans=0
for i in range(n):
    if d[i]>0: ans+=d[i]
print(ans)


n,m=map(int,input().split())
f=[[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    f[a-1][b-1]=c
for i in range(n):
    for j in range(n):
        if f[i][j]>0:
            for k in range(n):
                if f[j][k]>0:
                    buf=min(f[i][j],f[j][k])
                    f[i][j]-=buf
                    f[j][k]-=buf
                    f[i][k]+=buf
for i in range(n):
    f[i][i]=0
print(sum(map(sum,f)))

# -*- coding: utf-8 -*-

n, m = list(map(int, input().split()))
abc = [list(map(int, input().split())) for i in range(m)]

mat = [[0]*n for i in range(n)]
for t in abc:
    mat[t[0]-1][t[1]-1] = t[2]
    
total = 0
for i in range(n):
    s = sum(mat[i][:]) - sum([mat[x][i] for x in range(n)])
    if s < 0:
        continue;
    total += s
print(total)


R = lambda: map(int, input().split())
n, m = R()
p = [0] * n
for i in range(m):
  a, b, c = R()
  p[a - 1] -= c
  p[b - 1] += c
print(sum(i for i in p if i > 0))

n, m = map(int, input().split())
p = [0] * (n + 1)
for i in range(m):
    a, b, c = map(int, input().split())
    p[a], p[b] = p[a] - c, p[b] + c
print(sum(x for x in p if x > 0))

n, m = map(int, input().split())
e = [[0] * n for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    e[a - 1][b - 1] += c
    e[b - 1][a - 1] -= c
cnt = 0
for i in range(n):
    cnt1 = 0
    for j in range(n):
        cnt1 += e[i][j]
    cnt += abs(cnt1)
print(cnt // 2)

n,m = list(map(int, input().split()))
debt=[0]*(n+1)
for i in range(m):
	a,b,c = list(map(int, input().split()))
	debt[a]-=c
	debt[b]+=c
ans=0
for i in debt:
	if i>0:
		ans+=i
print(ans)


from sys import stdin

n, m = list(map(int, input().split()))
owes = [0 for i in range(n+1)]

for i in range(m):
    a, b, c = list(map(int, input().split()))
    owes[a] += c
    owes[b] -= c

sol = 0
for owe in owes:
    if (owe > 0):
        sol += owe

print(sol)


R = lambda: map(int, input().split())
n, m = R()
p = [0] * n
for i in range(m):
  a, b, c = R()
  p[a - 1] -= c
  p[b - 1] += c
print(sum(i for i in p if i > 0))

n,m=list(map(int,input().split()))
l=[0 for i in range(n+3)]
for i in range(m):
    x,y,c=list(map(int,input().split()))
    l[x]+=c
    l[y]-=c
s=0
for i in l:
    s+=max(i,0)
print(s)


n, m = list(map(int, input().split(' ')))
have = (n + 1) * [0]
for _ in range(m):
    person_1, person_2, owns_ = list(map(int, input().split(' ')))
    have[person_1] += owns_
    have[person_2] -= owns_

print(sum(i for i in have if i > 0))


n, m = list(map(int, input().split()))

ms = [[0, 0] for i in range(n)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    ms[a-1][0] += c
    ms[b-1][1] += c

sol = 0
for i in range(n):
    sol += max(ms[i][0] - ms[i][1], 0)

print(sol)


R = lambda: list(map(int, input().split()))

n, m = R()

p = [0] * n

for i in range(m):

  a, b, c = R()

  p[a - 1] -= c

  p[b - 1] += c

print(sum(i for i in p if i > 0))



# Made By Mostafa_Khaled


n,m=map(int,input().split())
baaki=[0]*15000
for i in range(m):
    x,y,cbaaki=map(int,input().split())
    baaki[x]+=cbaaki 
    baaki[y]-=cbaaki 
sm=0 
for i in baaki:
    if i>0:
        sm+=i 
print(sm)