"""Original bounded Johnson allpairs reweighting versus independent simple-path oracle."""
import heapq,json

def johnson(nodes,edges):
 if not isinstance(nodes,list) or not 1<=len(nodes)<=6 or len(set(nodes))!=len(nodes) or any(type(n)!=str for n in nodes) or not isinstance(edges,list) or len(edges)>16 or any(not isinstance(e,tuple) or len(e)!=3 or e[0] not in nodes or e[1] not in nodes or e[0]==e[1] or type(e[2])!=int or abs(e[2])>20 for e in edges) or len({(a,b) for a,b,c in edges})!=len(edges):raise ValueError('bounded simple directed weighted graph')
 # Allzero init is exact super-source with zero edges to every original node.
 h={a:0 for a in nodes};history=[]
 for it in range(len(nodes)):
  changed=False
  for a,b,c in edges:
   if h[b]>h[a]+c:h[b]=h[a]+c;changed=True
  history.append(dict(h))
  if not changed:break
  if it==len(nodes)-1:raise ValueError('global negative cycle')
 rw=[(a,b,c+h[a]-h[b]) for a,b,c in edges];assert all(c>=0 for a,b,c in rw);adj={a:[] for a in nodes}
 for a,b,c in rw:adj[a].append((b,c))
 distances={}
 for src in nodes:
  d={a:None for a in nodes};d[src]=0;heap=[(0,src)]
  while heap:
   cost,u=heapq.heappop(heap)
   if d[u]!=cost:continue
   for v,c in adj[u]:
    candidate=cost+c
    if d[v] is None or candidate<d[v]:d[v]=candidate;heapq.heappush(heap,(candidate,v))
  distances[src]={v:None if z is None else z-h[src]+h[v] for v,z in d.items()}
 return {'potential':h,'potential_history':history,'reweighted_edges':rw,'distances':distances}
def simple(nodes,edges,s,t):
 adj={n:[] for n in nodes}
 for a,b,c in edges:adj[a].append((b,c))
 found=[]
 def dfs(u,seen,cost):
  if u==t:found.append(cost)
  for v,w in adj[u]:
   if v not in seen:dfs(v,seen|{v},cost+w)
 dfs(s,{s},0);return min(found) if found else None

def demo():
 nodes=list('ABCDU');edges=[('A','B',2),('B','C',-4),('C','D',2),('A','D',1),('D','B',3)];result=johnson(nodes,edges);assert result['potential']=={'A':0,'B':0,'C':-4,'D':-2,'U':0}
 for s in nodes:
  for t in nodes:assert result['distances'][s][t]==simple(nodes,edges,s,t)
 assert result['distances']['A']['D']==0
 shifted=[(a,b,w+4) for a,b,w in edges];wrong=simple(nodes,shifted,'A','D');assert wrong==5 and result['distances']['A']['D']==0
 telescope=[]
 for path in [['A','D'],['A','B','C','D']]:
  cost=sum(next(w for a,b,w in edges if (a,b)==(u,v)) for u,v in zip(path,path[1:]));prime=sum(next(w for a,b,w in result['reweighted_edges'] if (a,b)==(u,v)) for u,v in zip(path,path[1:]));assert prime==cost+result['potential'][path[0]]-result['potential'][path[-1]];telescope.append({'path':path,'original_cost':cost,'reweighted_cost':prime})
 bad=[]
 for label,ns,es in [('negative_cycle',list('ABCDU'),edges+[('C','B',1)]),('separate_negative_cycle',list('ABCUV'),[('A','B',1),('U','V',-2),('V','U',1)]),('unknown',nodes,edges+[('A','Z',1)]),('parallel',nodes,edges+[('A','B',1)]),('bool_weight',nodes,[('A','B',True)]),('selfloop',nodes,[('A','A',1)]),('budget',list('ABCDEFG'),[])]:
  try:johnson(ns,es)
  except ValueError:bad.append(label)
  else:raise AssertionError(label)
 return {'nodes':nodes,'edges':edges,'johnson':result,'all_pairs_simple_path_oracles':25,'path_potential_telescoping':telescope,'wrong_add4_every_edge_AD_cost':wrong,'invalid_cases_rejected':bad,'scope':'Own max6nodes16edges integerexact, globalnegativecycleabort inclseparatecomponent. Bellman potentials then actual heap Dijkstra, no graph library or route/latency/product claim.'}
if __name__=='__main__':print(json.dumps(demo(),indent=2))