import math
import copy
import scipy.integrate as integrate


class Node:
    traffic = 0
    """(destination node, capacity)"""
    roads = []

    def __init__(self, traffic):
        self.traffic = traffic


class StateObject:
    capacity = 0
    improvement = 0
    repaired = 0

    def __init__(self, cap, imp):
        self.capacity = cap
        self.improvement = imp


class State:
    budget = 0
    array = []
    target = 0

    def __init__(self, budget, array=None):
        if array is None:
            self.array = []
            self.target = 0
        else:
            self.array = array
            for i in range(len(array)):
                self.target += array[i].improvement
        self.budget = budget

    def add_object(self, obj):
        self.array.append(obj)
        self.target += obj.improvement

    def generate_neighbours(self):
        neighbours = []
        for i in range(len(self.array)):
            state_obj = self.repair_road(i)
            if state_obj:
                neighbours.append(state_obj)
        return neighbours

    def repair_road(self, i):
        a = self.array[i].capacity
        b = self.array[i].improvement
        if b > 0:
            arr = copy.deepcopy(self.array)
            arr[i] = StateObject(a + 1, b - 1)
            cost = calculate_cost(a, a + 1)[0]
            if self.budget - cost > 0:
                return State(self.budget-cost, arr)
            return None

    def print(self):
        print("Budzet: " + str(self.budget))
        print("F-cja celu: " + str(self.target))
        for i in self.array:
            print("<" + str(i.capacity) + ", " + str(i.improvement) + ">")


def add_road(graph, node_a, node_b, capacity):
    graph[node_a].roads.append((node_b, capacity))
    graph[node_b].roads.append((node_a, capacity))


def read_input():
    graph = []
    budget = int(input("Budzet: "))
    start_state = State(budget)
    nodes = int(input("Liczba miast: "))
    roads = int(input("Liczba drog: "))
    for i in range(nodes):
        graph.append(Node(int(input("Podaj ruch z/do miasta " + str(i) + ": "))))
    for i in range(roads):
        a = int(input("droga z: "))
        b = int(input("do: "))
        c = int(input("przepustowosc: "))
        add_road(graph, a, b, c)
        start_state.add_object(StateObject(c, max(min(graph[a].traffic, graph[b].traffic)-c, 0)))
    return graph, budget, nodes, roads, start_state


def calculate_cost(a, b):
    return integrate.quad(lambda x: (math.atan(x-10)+math.pi/2)*40, a, b)


def dfs(state):
    for i in range(len(state.array)):
        while True:
            state2 = state.repair_road(i)
            if state2 is None:
                break
            state = state2
    return state


def vns(state):
    pass


def main():
    graph, budget, nodes, roads, start_state = read_input()
    print("Stan startowy")
    start_state.print()
    start_state_copy = copy.deepcopy(start_state)
    print("Stan koncowy dfs (naiwne polepszanie kolejnych drog)")
    dfs(start_state_copy).print()
    #print("Stan koncowy vns")
    #vns(start_state).print()


if __name__ == "__main__":
    main()