SUN인장 분자 만들기

화학과 대학원생 탐레프는 S, U, N 원자로 이루어진 분자를 만들려고 한다. 레프는 이미 분자 구조를 정했다. 원자를 정점, 두 원자의 결합을 간선으로 하면 레프의 분자 구조는 특이한 선인장 그래프가 된다. 특이한 선인장 그래프는 모든 정점이 하나 이하의 단순 사이클에만 포함되는 그래프이다.

레프는 아직 어느 위치에 어떤 원자를 놓을지 정하지 않았다. 레프는 같은 종류의 두 원자를 결합하는 방법을 모르기 때문에, 결합된 두 원자는 서로 다른 종류여야 한다. 각 위치에 S, U, N 원자를 놓는 데 드는 에너지가 주어질 때, 레프는 가장 안정한 분자를 만들고자 한다. 가장 안정한 분자는 모든 위치의 필요 에너지 합이 가장 낮은 분자이다.

레프는 실험을 통해 위치마다 원자를 놓는 데 필요한 에너지를 계속 수정한다. 에너지가 수정될 때마다 만들 수 있는 가장 안정한 분자의 필요 에너지 합을 레프에게 알려주자.

첫째 줄에 원자 수 N, 결합 수 M, 실험 횟수 Q가 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 줄에 위치 $i$에 S, U, N 원자를 놓는 데 필요한 에너지 Si, Ui, Ni가 공백으로 구분되어 주어진다. ($1 \le i \le N$)

이어서 M개의 줄에 $i$번째 결합이 연결하는 두 원자 위치의 번호가 공백으로 구분되어 주어진다. ($1 \le i \le M$)

마지막으로 Q개의 줄에 $i$번째 실험의 결과를 나타내는 정수 Ai, Bi, Ci가 공백으로 구분되어 주어진다. 이는 Ai번 위치에 Bi 원자를 놓는 데 필요한 에너지를 Ci로 수정한다는 뜻이다. Bi가 1이면 S, 2이면 U, 3이면 N 원자를 의미한다.

Q줄에 걸쳐, 필요한 에너지가 수정될 때마다 만들 수 있는 가장 안정한 분자의 필요 에너지 합을 한 줄에 하나씩 출력한다.

• 1 ≤ N ≤ 100,000
• M ≥ N - 1
• 1 ≤ Q ≤ 100,000
• 1 ≤ Si, Ui, Ni ≤ $10^4$ (1 ≤ i ≤ N)
• 주어지는 분자 구조가 이루는 그래프는 단순 그래프이다.
• 주어지는 분자 구조가 이루는 그래프는 연결 그래프이다.
• 주어지는 분자 구조가 이루는 그래프에서 모든 정점은 하나 이하의 단순 사이클에만 포함된다.
• 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ 3, 1 ≤ Ci ≤ $10^4$ (1 ≤ i ≤ Q)