题目链接（洛谷）
首先注意到一点：\(1\) 并不重要。即起点在哪并不是关键的。为什么？我经过一个节点时不一定要吃掉该点的糖果，而我一定要吃掉所有的糖果，所以我最初的宽度一定可以走到整个图。相当于我可以从任意节点出发。这一点说明设计状态时无需考虑起点。
我们只需要每一个糖都能吃到，即整张图是联通的。显然，我们只需要最大生成树上的边。显然，如果最大生成树上的边都走不了，通过其他边肯定也走不了。
考虑 kruskal 重构树，将一个图上问题转化成树上问题。
考虑根 \(u\) 的两棵子树，不妨记为 \(x\) 和 \(y\)。因为这里是第一个会被断开的地方，而树具有递归结构，从根节点考虑也是常见的。
我们需要将 \(x\) 和 \(y\) 内所有糖果都吃掉，则我先吃掉其中一棵子树，再通过 \(u\) 表示的整条边一定不劣。不然，我吃了一部分糖，然后穿过 \(u\) 表示的边，又需要回来。往返中必定有一次会吃完一棵子树中的糖然后穿过 \(u\) 表示的边。
考虑状态 \(f_u\) 表示走完 \(f_u\) 子树所需的最大的宽度。
我们假设先吃子树 \(x\)，则我们需要通过 \(u\) 这条边，需要满足 \(S_x + f_u \le w_u\)，其中 \(S_x\) 表示 \(x\) 的子树 \(c_i\) 和。然后我们走到 \(y\) 子树后我们还需要走完 \(y\) 的子树，所以 \(S_x +f_u \le f_y\)。
先吃子树 \(y\) 同理。所以有转移方程：
\[f_u = \max \{ \min \{ f_y -S_x,w_u - S_x\} ,\min \{ f_x -S_y,w_u - S_y\} \}
\]
注意边界为叶子节点，叶子节点表示原图中的点，没有限制。
最后放一下代码。
code
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;// 重构树需要，开两倍结点
struct edge{int u,v,w;bool operator<(const edge &o)const{return w>o.w;}
}es[N];
long long c[N],f[N];//c -> S
int n,m;
namespace KRT{int pre[N],bel[N];int ch[N][2],pj[N];int ncnt;int find(int x){return bel[x]=bel[x]==x?x:find(bel[x]);}void init(){for(int i=1;i<N;i++) bel[i]=i;ncnt=n;}void merge(int x,int y,int h){x=find(x),y=find(y);if(x==y) return ;ncnt++;pre[x]=pre[y]=bel[x]=bel[y]=ncnt;ch[ncnt][0]=x,ch[ncnt][1]=y;pj[ncnt]=h;f[ncnt]=max(min(f[y]-c[x],h-c[x]),min(f[x]-c[y],h-c[y]));c[ncnt]=c[x]+c[y];}
}
int main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++) {cin>>c[i];f[i]=LONG_LONG_MAX;}//叶子结点无限制for(int i=1;i<=m;i++)cin>>es[i].u>>es[i].v>>es[i].w;sort(es+1,es+m+1);KRT::init();for(int i=1;i<=m;i++){KRT::merge(es[i].u,es[i].v,es[i].w);}if(KRT::ncnt<n*2-1||f[KRT::ncnt]<=0)printf("-1");else printf("%lld",f[KRT::ncnt]);return 0;
}