class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        # 1. Calculate net balance for each person
        person_balance = defaultdict(int)
        for u, v, amount in transactions:
            person_balance[u] -= amount
            person_balance[v] += amount
        
        # 2. Filter out people who are already settled (0 balance)
        # We only care about non-zero balances.
        debts = [b for b in person_balance.values() if b != 0]
        
        return self.dfs(0, debts)

    def dfs(self, start_index: int, debts: List[int]) -> int:
        # Skip people who have already been settled (balance is 0)
        while start_index < len(debts) and debts[start_index] == 0:
            start_index += 1
        
        # Base case: If we've gone through everyone, 0 transactions needed
        if start_index == len(debts):
            return 0
        
        min_transactions = float('inf')
        
        # Try to settle the current person's debt (debts[start_index])
        # by combining it with a subsequent person (debts[i])
        for i in range(start_index + 1, len(debts)):
            
            # Optimization: Only attempt to settle if they have opposite signs.
            # (One owes money, the other is owed money).
            if debts[start_index] * debts[i] < 0:
                
                # "Transfer" balance from start_index to i. 
                # We effectively zero out debts[start_index] and add it to debts[i].
                debts[i] += debts[start_index]
                
                # 1 transaction + result of the recursive call
                min_transactions = min(min_transactions, 1 + self.dfs(start_index + 1, debts))
                
                # Backtrack: Undo the transfer for the next iteration
                debts[i] -= debts[start_index]
                
        return min_transactions