[COCI2008-2009#6] SLICICE

题目背景

在一个城市里，有群孩子热衷于收集卡片。

题目描述

由于他们的零花钱不够，所以想出了一个办法：两人一组，每人出一半的钱，到商店购买两张卡片。紧接着，他们比赛谁先跑到市中心的喷泉，获胜者将得到这两张卡片。如果两人同时到达，那么每人将拿走一张。 有一天，所有的孩子聚集在了一起。他们想统计出所有的购买记录。但是孩子们的记忆有些模糊了，只记得一部分购买记录（且不知道谁得到了多少），并且数出了自己有多少张卡片。你需要编写一个程序，帮助孩子们还原一种可能的购买记录。

输入输出格式

输入格式


输入第一行两个整数 $n,m$，表示孩子的数量和孩子们记忆中的购买记录。孩子从 $1\sim n$ 编号。 第二行 $n$ 个整数，表示每个孩子所拥有的卡片的数量。 接下来的 $m$ 行，每行两个整数 $a,b$，表示编号分别为 $a,b$ 的两个孩子一起去买了一次卡片。

输出格式


输出第一行一个整数 $k$，表示购买总数。 接下来的 $k$ 行，每行三个整数。前两个整数为一次购买中两个孩子的编号。第三个整数为前一个孩子在这次比赛中获得的卡片数（$0/1/2$）。 **题目保证有解。购买的总数最多为 $1000$。如果有多种购买的方案，输出任意一种，本题使用 SPJ。**

输入输出样例

输入样例 #1

2 3
5 1
1 2
1 2
1 2

输出样例 #1

3
1 2 1
1 2 2
1 2 2

输入样例 #2

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

输出样例 #2

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

输入样例 #3

5 0
3 0 2 4 1

输出样例 #3

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

说明

#### 数据规模与约定 对于 $100\%$ 的数据，保证 $1\le n\le 100$，$0\le m\le 1000$。 #### 说明 **题目译自 [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T6 SLICICE***。