 Graph Traversal with Tree-Like Structure

We have a graph which looks similar to a tree structure, like that. In particular, the nodes are only connected to their nodes below.

Node   Node
/    \  /  \
Node  Node   Node
\     \
Node   Node

The input for such (but not the one above) graph looks like that:

4 5
1 2 10
2 3 20
1 4 10
3 4 25
2 4 30

In the first line, we have the 4, which specifies that we have 4 nodes in the graph. 5 means, we have 5
edges. The following lines (1, 2, 10), (2, 3,20)… read as follows:

There is an edge from Node 1 to Node 2 with the cost of 10
There is an edge from Node 2 to Node 3 with the cost of 30 and so on.
The goal is to find the highest cost for any path in the graph.

The output, or the max cost would be by traversing the path (1 → 2 → 3 → 4) and would give a cost of 55.

I tried to code it and came up with this:

T = int(input())

def dfs(graph, node, dp, visited):

cur, dist = node, node
visited[cur] = True
for neighbor in graph[cur]:
n_idx, n_dist = neighbor, neighbor
if not visited[n_idx]:
dfs(graph, neighbor, dp, visited)
dp[cur] = max(dp[cur], dp[n_idx] + n_dist)

res = max(res, dp[cur])

for j in range(T):
vertices, edges = [int(x) for x in input().split()]
graph = [[] for _ in range(vertices + 1)]
dp =  * (position + 1)
for _ in range(vertices):
node = [int(y) for y in input().split()]
node_idx = node
graph[node_idx].append((node, node))

res = 
visited = [False] * (position + 1)
for i in range(1, position + 1):
if not visited[i] and len(graph[i]) > 0:
dfs(graph, (i, 0), dp, visited)

print(f"Case #{j + 1}: {res}")

This code returns a run error, and exceeds time limit if I remove the

if not visited[n_idx]:
dfs(graph, neighbor, dp, visited)

condition in the DFS function. I would really appreciate any help!

Where did you define/declare the variable position?

That is actually a typo and should be the vertices. I just forgot to translate it. I have fixed it