Farmer John 太懒，不想维护现在能到达全部 $N$ 个牧场（$5\le N\le10{,}000$，编号 $1\ldots N$）的牛路。每个牧场恰有一头牛。他计划在保持连通的前提下尽量移除 $P$ 条路（$N-1\le P\le100{,}000$）。你须决定保留哪 $N-1$ 条。
双向路 $j$ 连接 $S_j,E_j$（$1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$），通行耗时 $L_j$（$0\le L_j\le1{,}000$）。每对牧场之间直接道路最多一条。
交通系统缩减令牛伤心。你每天至少拜访每头牛一次让她开心。每次访问牧场 $i$（即使只是路过），都要花 $C_i$ 时间（$1\le C_i\le1{,}000$）与牛交谈。
直到牛不再伤心，你每晚在自己选定的同一牧场睡觉。因此至少早晨醒来、傍晚回去睡觉时，都要与那里的牛交谈。
假定 FJ 按你建议保留道路，且你选择最佳睡觉牧场，求每天拜访每头牛至少一次的最少总时间。
前 $10$ 次提交，你会得到程序在部分真实测试数据上运行的结果。
输入格式
第 $1$ 行：空格分隔的整数 $N,P$。
第 $2\ldots N+1$ 行：第 $i+1$ 行包含整数 $C_i$。
第 $N+2\ldots N+P+1$ 行：第 $N+j+1$ 行包含空格分隔的整数 $S_j,E_j,L_j$。
输出格式
- 第 $1$ 行：一个整数，拜访全部牛的总时间，包括对睡觉牧场牛的两次拜访。
样例
输入格式 1
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12输出格式 1
176说明
+-(15)-+
/ \
/ \
1-(5)-2-(5)-3-(6)--5
\ /(17) /
(12)\ / /(12)
4------+保留这些道路：
1-(5)-2-(5)-3 5
\ /
(12)\ /(12)
*4------+在牧场 $4$ 醒来，按 $4,5,4,2,3,2,1,2,4$ 拜访，睡前共花 $176$ 时间。
子任务
分值：$300$
题目作者：David Benjamin 和 Jacob Steinhardt，2008 年