太戈编程的944，武林大会4

作为武林盟主，你希望邀请各门派高手来武林大会切磋武艺。共有n个门派，分散在江湖上不同位置，编号1到n，大会将在1号门派举办。对于第i个门派，你打算邀请xi个人参会。各门派间有m条单向通路，第i条路从ai门派到bi门派，走这一段路每人路费为ci，可能是负数代表每次走一遍该路段能发现财宝，如有剩余财宝会上缴盟主。本次武林大会的所有路费由你承担，所有财宝也由你收缴，请问总费用至少多少？可能为负数。

如某个门派不能到达1号门派那就忽略该门派，两个门派间可以存在多条路。

如某个能去开会的门派在去1号门派的路上发现负权回路，那大家就无心开会，输出-1。

输入输出格式
输入格式
输入文件wulin4.in 第一行为正整数n，n<=2000。第二行共n个数代表xi，均不超过100。下一行为正整数m，m<=100000。接着m行，每行三个整数ai,bi和ci。1<=ai,bi<=n，-10000<=ci<=10000。
输出格式
输出文件wulin4.out 输出一个整数。
输入输出样例
输入样例#1:
2
100 90
1
2 1 5
输出样例#1:
450
输入样例#2:
3
10 10 10
3
2 1 -2
3 2 3
3 1 4
输出样例#2:
-10
输入样例#3:
4
1 2 3 4
3
1 2 -1
3 1 -1
2 3 1
输出样例#3:
-1

就是SPFA……但是不想写，求代码，谢谢！