### 问题描述 在“盛夏！海岛？大冒险！”活动中，你和可莉被邀请到一个由 $N$ 个海岛组成的方形大陆。每个海岛上都有一些“亮闪闪的漂流物”（以下简称宝物）等待你们去收集，这些海岛之间有一些桥梁连接。 你的任务是从 $1$ 号岛屿开始，每次访问目标是一个未收集过宝物的小岛，你需要把这个岛屿的所有宝物都收集起来，且收集完一个小岛的宝物后会**立刻被传送回 $1$ 号小岛**，传送不消耗时间，并再次出发前往下一个小岛，直到所有的小岛都访问完毕。 请你设计一个算法，找出把所有海岛的宝物都收集起来的最短时间。 ### 输入格式 第一行输入两个整数 $N$ 和 $M$，分别表示海岛的数量和桥的数量。$1\leq N\leq 100$， $0\leq M\leq \frac{N\times (N-1)}{2}$。 第二行输入 $N$ 个整数，按顺序给出收集每个海岛上的宝物所需要的时间 $T_1,T_2...T_i...T_N$，$1\leq T_i\leq 10^3$。 接下来的 $M$ 行，每行有三个整数 $a$，$b$，$d$，表示从 $a$ 岛到 $b$ 岛有一座桥，通过所需要的时间为 $d$。$1\leq a,b\leq N$，$a≠b$，$1\leq d\leq 10^3$。 ### 输出格式 输出一行，表示最少需要的时间。如果不能收集到所有海岛的宝物，那么输出 $-1$。 ### 输入样例 ``` 6 6 1 1 4 5 1 4 1 2 1 2 3 4 3 4 7 4 5 10 1 5 13 1 6 7 ``` ### 输出样例 ``` 54 ``` ### 测评数据规模 对于 40% 的数据，$1\leq N\leq 10$，$1\leq M\leq 20$，$1\leq T_i\leq 100$，$0\leq d\leq 100$。 对于 80% 的数据，$1\leq N\leq 50$，$1\leq M\leq 1000$，$1\leq T_i\leq 1000$，$0\leq d\leq 1000$。 对于 100% 的数据，$1\leq N\leq 100$，$1\leq M\leq 5000$，$1\leq T_i\leq 1000$，$0\leq d\leq 1000$。