"""Authored finite directed integer graph: negative edges versus reachable negative cycles."""
import json,platform
def solve(nodes,edges,source):
 if not 1<=len(nodes)<=8 or source not in nodes or len(edges)>32:raise ValueError('bounded graph')
 if len(set(nodes))!=len(nodes) or any(a not in nodes or b not in nodes or type(w) is not int or abs(w)>100 for a,b,w in edges):raise ValueError('edge contract')
 dist={v:None for v in nodes};dist[source]=0;pred={};passes=[];last=None
 for step in range(len(nodes)):
  last=None
  for a,b,w in edges:
   if dist[a] is not None and (dist[b] is None or dist[b]>dist[a]+w):dist[b]=dist[a]+w;pred[b]=(a,w);last=b
  passes.append({'pass':step+1,'distances':dict(dist),'changed':last is not None})
  if last is None:break
 if last is not None and len(passes)==len(nodes):
  v=last
  for _ in nodes:v=pred[v][0]
  cycle=[v];u=pred[v][0]
  while u!=v:
   cycle.append(u);u=pred[u][0];assert len(cycle)<=len(nodes)
  cycle.append(v);cycle=list(reversed(cycle));weights={(a,b):w for a,b,w in edges}
  total=sum(weights[a,b] for a,b in zip(cycle,cycle[1:]));assert total<0
  return {'reachable_negative_cycle':True,'finite_distance_vector_valid':False,'distances':None,'cycle':cycle,'cycle_weight':total,'passes':passes}
 paths={}
 for end in nodes:
  if dist[end] is None:paths[end]=None;continue
  p=[end]
  while p[-1]!=source:p.append(pred[p[-1]][0]);assert len(p)<=len(nodes)
  paths[end]=list(reversed(p))
 return {'reachable_negative_cycle':False,'finite_distance_vector_valid':True,'distances':dist,'paths':paths,'passes':passes}
def simple_path_oracle(nodes,edges,source):
 adj={v:[] for v in nodes}
 for a,b,w in edges:adj[a].append((b,w))
 best={v:None for v in nodes}
 def visit(v,path,total):
  if best[v] is None or total<best[v]:best[v]=total
  for u,w in adj[v]:
   if u not in path:visit(u,path+[u],total+w)
 visit(source,[source],0);return best
def demo():
 nodes=list('ABCDU');edges=[('A','B',4),('A','C',5),('B','C',-2),('C','D',3),('B','D',10)]
 finite=solve(nodes,edges,'A');oracle=simple_path_oracle(nodes,edges,'A');assert finite['distances']==oracle=={'A':0,'B':4,'C':2,'D':5,'U':None}
 neg_edges=[('A','B',4),('B','C',-3),('C','B',1),('C','D',2)];negative=solve(nodes,neg_edges,'A');assert negative['reachable_negative_cycle'] and negative['cycle_weight']==-2 and negative['distances'] is None
 witness_start=negative['cycle'][0];reachable=simple_path_oracle(nodes,neg_edges,'A')[witness_start];assert reachable is not None
 reach_path=['A','B','C'];weightmap={(a,b):w for a,b,w in neg_edges};assert reach_path[-1]==witness_start and sum(weightmap[a,b] for a,b in zip(reach_path,reach_path[1:]))==reachable
 disconnected_edges=[('A','B',4),('C','D',-3),('D','C',1)];disconnected=solve(nodes,disconnected_edges,'A');assert not disconnected['reachable_negative_cycle'] and disconnected['distances']=={'A':0,'B':4,'C':None,'D':None,'U':None}
 repeated=[reachable+i*negative['cycle_weight'] for i in range(4)];assert all(b<a for a,b in zip(repeated,repeated[1:]))
 return {'runtime':platform.python_version(),'negative_edge_no_cycle':{'edges':[list(e) for e in edges],'result':finite,'simple_paths_oracle':oracle},'reachable_negative_cycle':{'edges':[list(e) for e in neg_edges],'result':negative,'reachable_cycle_start_simple_path':reach_path,'reachable_cycle_start_simple_path_cost':reachable,'cost_after_zero_to_three_cycle_repetitions':repeated},'unreachable_negative_cycle':{'edges':[list(e) for e in disconnected_edges],'result':disconnected},'scope':'Only fixed small directed integer fixtures, V-1 relaxation sweeps plus extra detection round; reachable-cycle result refuses all final finite distances. Not discounted MDP, Java/NetworkX execution or production routing.'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))