type 'a poids = Poids of 'a | Infini;;

let rec insere i x l =
  match l with
  | [] -> [i]
  | t::q -> if x > t then i :: l else t :: (insere i x q)
;;

let liste_triee_arrete w =
  let l = ref [] and n = List.length w in
  for i = 0 to n - 2 do
    for j = i + 1 to (n - 1) do
      match (List.nth w i).(j) with
      | Poids(p) -> l := insere (i, j) p !l
      | Infini -> ()
    done;
  done;
  !l
;;

let g = [
  [Infini; Poids(9); Infini; Poids(5); Infini; Infini; Infini];
  [Poids(7); Infini; Poids(8); Poids(9); Poids(7); Infini; Infini];
  [Infini; Poids(8); Infini; Infini; Poids(5); Infini; Infini];
  [Poids(5); Poids(9); Infini; Infini; Poids(15); Poids(6); Infini];
  [Infini; Poids(7); Poids(5); Poids(15); Infini; Poids(8); Poids(9)];
  [Infini; Infini; Infini; Poids(6); Poids(8); Infini; Poids(11)];
  [Infini; Infini; Infini; Infini; Poids(9); Poids(11); Infini];
];;

let aretes = liste_triee_arrete g;;