차수 제한 최소 스패닝 트리

스패닝 서브그래프(Spanning Subgraph)는 원래 그래프의 모든 정점을 포함하는 서브그래프를 말한다. 스패닝 서브그래프가 트리이면 이를 스패닝 트리(Spanning Tree)라고 한다.

그래프와 간선의 비용이 주어질 때, 간선 비용의 합이 최소인 스패닝 트리를 구하는 다항 시간 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘 등이 있으며, 중급 강의에서 다룬다.

국렬이는 여기에 제약을 하나 더 추가하려고 한다. 정점마다 양의 정수 $b_1$, ..., $b_N$이 주어지고, 정점 $i$의 차수가 $b_i$를 넘지 않도록 스패닝 트리를 만들려고 한다. 정점의 차수는 그 정점에 인접한 간선의 개수이다.

이렇게 만들어진 스패닝 트리 중에서 간선 비용의 합이 최소인 스패닝 트리를 구하라.

첫째 줄에 그래프의 정점 개수 $N$($1 \le N \le 10$)과 간선의 개수 $M$($0 \le M \le 27$)이 주어진다.

둘째 줄에 $N$개의 자연수 $b_1$, ..., $b_N$이 주어진다. ($0 \le b_i \le N-1$)

다음 $M$개의 줄에는 간선 정보를 나타내는 세 정수 $A$, $B$, $C$가 주어진다. 이는 $A$번 정점과 $B$번 정점이 비용 $C$인 간선으로 연결되어 있다는 뜻이다. 같은 정점 쌍을 잇는 간선은 두 개 이상 존재하지 않는다. ($A < B$, $\left| C \right| \le 1000000$)

제약을 만족하는 스패닝 트리가 존재하면 첫째 줄에 YES를 출력한다. 이어서 그 스패닝 트리의 간선을 $N-1$개의 줄에 걸쳐 출력한다. 간선을 출력하는 순서는 상관없으며, 각 간선은 두 정점 번호 중 작은 번호부터 출력한다. 비용 합이 최소인 스패닝 트리가 두 개 이상이면 그중 아무것이나 출력한다.

제약을 만족하는 스패닝 트리가 없으면 NO를 출력한다.