题目1： 小李希望开车到全国各地旅游，他发现旅途中各个城市的汽油价格也不相同，显然如果能够采取合理的加油方式，将会节省整个旅途的费用。假设汽车开始时油箱为空，汽车每走一个单位的距离将耗费一个单位的汽油。请帮助小李找到一种最省钱的方式完成他的整个自驾游。
输入要求：
输入的第一行包含两个整数n （1 ≤ n ≤ 1000）和m（0 ≤ m ≤ 10000），分别表示城市的数量以及道路的数量。其后的一行包含n个整数，分别表示n个城市的汽油价格。其后的m行，每一行包含三个整数u,v,d，表示城市u，v之间的距离为d（1 ≤