카페 컵 보관대 옮기기

문제

카페에는 깨끗한 컵을 보관하는 보관대가 N개 있다. 보관대에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 보관대에 처음 놓인 컵의 수가 주어지며, 컵이 하나도 없는 보관대도 있을 수 있다. 모든 컵은 같은 종류이고, 보관대에는 컵을 쌓을 수 있는 공간이 충분하다. 직원은 영업 준비를 하면서 컵 이동 요청 M개를 기록했다. 각 요청에는 출발 보관대 번호 A, 도착 보관대 번호 B, 옮기고 싶은 컵의 수 K가 적혀 있다. 요청을 처리할 때 출발 보관대에 컵이 K개 이상 있으면 정확히 K개를 옮긴다. 출발 보관대의 컵이 K개보다 적으면 그곳에 있는 컵을 모두 옮긴다. 따라서 요청한 수량을 전부 옮기지 못하더라도 가능한 수량은 반드시 이동한다. 출발 보관대가 비어 있다면 실제로 옮기는 컵의 수는 0개다. 요청은 입력에 주어진 순서대로 하나씩 처리한다. 한 요청으로 바뀐 컵의 수는 바로 다음 요청에 반영된다. 처음 상태를 기준으로 여러 요청을 동시에 처리하지 않는다. 출발 보관대와 도착 보관대의 번호는 항상 다르며, 이동 과정에서 컵이 새로 생기거나 사라지는 일은 없다. 직원이 별도로 컵을 가져가거나 보충하는 일도 없다. 카페 관리자는 모든 요청을 처리한 뒤 보관대마다 컵이 몇 개 남았는지 확인하려 한다. 또한 실제로 옮긴 수량이 요청한 K개보다 적었던 요청의 개수를 알고 싶어 한다. 이런 요청은 부족한 컵의 개수와 관계없이 한 번으로 센다. 예를 들어 5개를 요청했는데 3개만 옮긴 경우와 한 개도 옮기지 못한 경우는 각각 부족 요청 한 번이다. 같은 보관대에서 부족 요청이 여러 번 발생하면 각각 센다. 모든 이동 요청을 순서대로 처리하고 최종 상태와 부족 요청의 개수를 구한다.

입력

첫째 줄에 정수 N과 M이 공백으로 주어진다. 2 ≤ N ≤ 20000, 1 ≤ M ≤ 20000이다.
둘째 줄에 각 보관대의 처음 컵 수 C_1, C_2, …, C_N이 공백으로 주어진다. 모두 정수이며 0 ≤ C_i ≤ 1000이다.
다음 M개 줄에 정수 A, B, K가 공백으로 주어진다. 1 ≤ A, B ≤ N, A ≠ B, 1 ≤ K ≤ 1000이다.

출력

첫째 줄에 모든 요청을 처리한 뒤 각 보관대에 남은 컵의 수를 1번부터 N번까지 공백으로 구분하여 출력한다. 둘째 줄에 실제 이동 수량이 K보다 적었던 요청의 개수를 출력한다. 그런 요청이 없으면 0을 출력한다.

3 4
4 0 2
1 2 3
2 3 5
3 1 4
2 1 1

5 0 1
2

2 2
0 0
1 2 1
2 1 1

0 0
2

2 2
3 2
1 2 3
2 1 5

5 0
0

출처: Devin.KR 자체 제작