Как посчитать суммарный вес путей ориентированного взвешенного графа в DFS за одну итерацию?

G = (V,E) - ориентированный взвешенный граф.

D -> G (w:4)
D -> C (w:2)
D -> E (w:2)
C -> F (w:5)
C -> A (w:4)
B -> D (w:3)
B -> E (w:10)
G -> F (w:1)
E -> G (w:6)
A -> D (w:1)
A -> B (w:2)

изображение

Я использую DFS, чтобы найти все простые пути между узлом START=A и узлом END=F:

def find_all_paths(self, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if start not in self.edges:
            return []
        paths = []
        for node in self.edges[start]:
            if node not in path:
                paths.extend(self.find_all_paths(node, end, path))
        return paths

Результат:

['A', 'D', 'G', 'F']
['A', 'D', 'C', 'F']
['A', 'D', 'E', 'G', 'F']
['A', 'B', 'D', 'G', 'F']
['A', 'B', 'D', 'C', 'F']
['A', 'B', 'D', 'E', 'G', 'F']
['A', 'B', 'E', 'G', 'F']

Мне нужно получить такой результат:

['A', 'D', 'G', 'F'], TOTAL_WEIGHT_OF_PATH = 6
['A', 'D', 'C', 'F'], TOTAL_WEIGHT_OF_PATH = 8
['A', 'D', 'E', 'G', 'F'], TOTAL_WEIGHT_OF_PATH = 10
....
....

Где TOTAL_WEIGHT_OF_PATH — сумма весов для каждого ребра в пути. Конечно, я мог бы просто подсчитать значение TOTAL_WEIGHT_OF_PATH после получения результата DFS, но мне нужно рассчитать его в шагах DFS для поиска отсечения в условиях, основанных на TOTAL_WEIGHT_OF_PATH (например, TOTAL_WEIGHT_OF_PATH должно быть ‹ MAX_WEIGHT_OF_PATH)