from collections import defaultdict
from heapq import heapify, heappop, heappush

class Solution:
    def solve(self, connections):
        start = 0
        target = max(max(y, x) for y, x, _ in connections)

        adj = defaultdict(list)
        for f, t, id in connections:
            adj[f].append((t, id))

        hp = [(0, start, -1)]
        seen = defaultdict(set)

        while hp:
            cost, cur_pos, cur_bus = heappop(hp)
            if cur_pos == target:
                return cost
            if cur_bus in seen[cur_pos]:
                continue
            seen[cur_pos].add(cur_bus)

            for nex_pos, nex_bus in adj[cur_pos]:
                next_cost = cost
                if nex_bus != cur_bus:
                    next_cost += 1
                heappush(hp, (next_cost, nex_pos, nex_bus))

        return -1

ob = Solution()
matrix = [
    [0, 1, 0],
    [1, 2, 0],
    [2, 3, 0],
    [3, 5, 1],
    [5, 0, 2]
]
print(ob.solve(matrix))

matrix = [[0, 1, 0],  
[1, 2, 0],  
[2, 3, 0],  
[3, 5, 1],  
[5, 0, 2]]

2