import heapq

def solution(N, routes):
    graph = [[] for _ in range(N)]

    for start, end, cost in routes:
        graph[start].append((end, cost))

    INF = float('inf')
    distance = [INF] * N
    distance[0] = 0

    pq = [(0, 0)]

    while pq:
        dist, now = heapq.heappop(pq)

        if dist > distance[now]:
            continue

        for next_node, cost in graph[now]:
            new_cost = dist + cost

            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))

    if INF in distance:
        return -1

    return max(distance)


N = 4
routes = [
    [0, 1, 1],
    [0, 2, 4],
    [1, 2, 1],
    [2, 3, 1]
]

print(solution(N, routes))