【题目描述】

某地分布着N个村庄，编号0到N-1,每个村庄要么需要买酒，要么需要卖酒。
设第i个村庄对葡萄酒的需求为Ai,其中Ai>0表示该村需要买酒，Ai<0表示该村需要卖酒。所有村庄供需平衡,即所有Ai之和等于0 (∑Ai =0)。
不过，只有M对村庄之间存在贸易往来，其中第i对村庄之间无论运输多少葡萄酒，都要花费Ti的运费。请你计算最少需要多少运费就可以满足所有村庄对酒的需求。

【输入格式】

第一行两个整数N、M。
第二行N个整数Ai。
接下来M行每行三个整数pi,qi,Ti，表示在编号为pi和qi的村庄之间运酒需要花费Ti的费用。数据保证每对pi、qi最多出现一次。

【输出格式】

输出一个整数表示答案。无解输出 Impossible

【样例输入】

3 3
50 -20 -30
0 1 10
1 2 20
0 2 100

【样例输出】

30

【数据范围】

对于 50% 的数据：2<=N<=8。
对于 100% 的数据：2<=N<=16，0<=M<=N*(N-1)/2，0<=pi,qi<N，-1000<=Ai<=1000，0<=Ti<=1000

【限制】

本题时间限制1s，空间限制128MB（128000KB）。
共10个测试点，每个10分，忽略多余空格和换行。