from PIL import Image

#TODO:
# weight for each edge between nodes
# create szm matrix
# create El struktura
# bfs - save the first path from s to t
# ford: get the maximum flow, save the matrix
# get minimal cut based on the matrix generated by ford


IMG_SIZE = 10
NODES = 6
SOURCE = 0
SINK = 5

# img = Image.open('test.png', 'r')
# pixels = list(img.getdata())    

# pixel_matrix = [[] for _ in range(IMG_SIZE)]
szm_matrix = [[0 for _ in range(NODES)] for _ in range(NODES)]


def cost_func(ci, cj, i, j):
    current_rgb = pixel_matrix[ci][cj]
    next_rgb = pixel_matrix[i][j]
    rgb_diff = abs(current_rgb[0] - next_rgb[0]) + abs(current_rgb[1] - next_rgb[1]) + abs(current_rgb[2] - next_rgb[1])
    if rgb_diff == 0:
        return  100
    else:
        return (1/(abs(current_rgb[0] - next_rgb[0]) + abs(current_rgb[1] - next_rgb[1]) + abs(current_rgb[2] - next_rgb[1])))*100

def create_matrix():
    #create matrix from image pixels
    k = 0
    for index, value in enumerate(pixels):
        pixel_matrix[k].append(value)
        k += 1
        if k == IMG_SIZE:
            k = 0

    # create nodes from each pixel
    csp = 0
    for csp in range(NODES):
        current_i = int(csp/IMG_SIZE)
        current_j = csp%IMG_SIZE
        for i in range(current_i, IMG_SIZE):
            if i == current_i:
                for j in range(current_j+1, IMG_SIZE):
                    szm_index = i*IMG_SIZE + j
                    szm_matrix[csp][szm_index] = cost_func(current_i, current_j, i, j)
                    szm_matrix[szm_index][csp] = 0
            else:
                for j in range(current_j, IMG_SIZE):
                    szm_index = i*IMG_SIZE + j
                    szm_matrix[csp][szm_index] = cost_func(current_i, current_j, i, j)
                    szm_matrix[szm_index][csp] = 0

    # add source and sink nodes
    for csp in range(IMG_SIZE):
        szm_matrix[NODES][csp] = 10000 # -> source
        szm_matrix[NODES-csp-1][NODES+1] = 10000 # -> sink

def print_szm():
    for i in range(NODES):
        for j in range(NODES):
            print(szm_matrix[i][j], end=' ')
        print()

def dfs(current, finish, visited, path):
    visited[current] = True
    path.append(current)
    if current == finish:
        return True
    for i in range(NODES+2):
        if szm_matrix[current][i] > 0 and visited[i] == False:
            found = dfs(i, finish, visited, path)
            if found:
                return found
    path.pop()
    return False

def bfs(start, finish, parents):
    visited = [False] * (NODES)
    visited[start] = True
    Q = []
    Q.append(start)

    while Q:
        current = Q.pop(0)

        if current == finish:
            return True

        for i in range(NODES):
            if szm_matrix[current][i] > 0 and not visited[i]:
                Q.append(i)
                parents[i] = current
                visited[i] = True
    
    return False
    

def find_min_capacity_in_path(path):
    i = 0
    min_edge = 100000
    while i < len(path)-1:
        if szm_matrix[path[i]][path[i+1]] < min_edge:
            min_edge = szm_matrix[path[i]][path[i+1]]
        i += 1
    return min_edge

def change_capacity_and_flow(path, min_capacity):
    i  = 0
    while i < len(path) - 1:
        From = path[i]
        To = path[i+1]
        # print("BEFORE: ")
        # print(From, To, szm_matrix[From][To], szm_matrix[To][From])
        szm_matrix[From][To] -= min_capacity
        szm_matrix[To][From] += min_capacity
        # print("AFTER: ")
        # print(From, To, szm_matrix[From][To], szm_matrix[To][From])
        i += 1

def print_path_capacities(path):
    i  = 0
    while i < len(path) - 1:
        From = path[i]
        To = path[i+1]
        print(From, To, szm_matrix[From][To], szm_matrix[To][From])
        i += 1

def Ford_Fulkerson():
    van = True

    while van:
        visited = [False for x in range(NODES+2)]
        path = []
        van = dfs(SOURCE, SINK, visited, path)
        if van:
            #print(path)
            min_capacity = find_min_capacity_in_path(path)
            change_capacity_and_flow(path, min_capacity)

def trace_path(current, parents, path):
    if parents[current] == -1:
        path.append(current)
        return
    trace_path(parents[current], parents, path)
    path.append(current)

def Edmonds_Karp():
    found = True
    counter = 0
    max_flow = 0
    while found:
        parents = [-2] * (NODES)
        parents[SOURCE] = -1
        path = []
        found = bfs(SOURCE, SINK, parents)
        if found:
            trace_path(SINK, parents, path)
            min_capacity = find_min_capacity_in_path(path)
            change_capacity_and_flow(path, min_capacity)
            max_flow += min_capacity
            # print(min_capacity)
        counter += 1
    
    # print_szm()
    # print(counter)
    # print(max_flow)
    return max_flow

def minimal_cut():
    visited = [False] * (NODES)
    visited[SOURCE] = True
    Q = []
    Q.append(SOURCE)

    while Q:
        current = Q.pop(0)
        for i in range(NODES):
            if szm_matrix[current][i] > 0 and not visited[i]:
                Q.append(i)
                visited[i] = True
    
    # for i in range(NODES):
    #     if visited[i] and i != SOURCE:
    #         print("SOURCE " + str(i))
    #     elif not visited[i] and i != SINK:
    #         print("SINK: " + str(i))


def main():
    #create_matrix()
    #Ford_Fulkerson()
    global NODES
    global SOURCE
    global SINK
    with open("maxflow.in", "r") as inp:
        lines = inp.readlines()
        for ind, line in enumerate(lines):
            if ind == 0:
                NODES, EDGES = line.split()
                NODES = int(NODES)
                SOURCE = 0
                SINK = NODES-1
            else:
                line = line.split()
                u = int(line[0])-1
                v = int(line[1])-1
                cost = int(line[2])
                szm_matrix[u][v] = cost
    with open("maxflow.out", "w") as out:
        out.write(str(Edmonds_Karp()))
    #minimal_cut() 
   


if __name__ == '__main__':
    main()