题目大意
给定一个有 \(n\) 个结点和 \(m\) 条边的带权无向图，每个结点 \(i\) 上有 \(c_i\) 头奶牛， 1 号结点为家，每次回家奶牛会走一条最短的路径，如果有多条长度相同的最短路径，则奶牛会走字典序最小的一条。现在，你可以增加一条从 1 到任意结点的长度为给定值 \(T\) 的一条边。如果一头奶牛在平时回家的路上经过了这条边相连的结点，且这条边能使其回家路径更短，则其会走这条边。求能使所有奶牛走的路径长度和的变化的最大值。

解题思路
就是对于一个图，构造一棵树，使从源点开始的单源最短路径与原图一模一样。怎么做呢，跑一边Dijkstra，然后对于一个点 u，枚举它的边，设当前的边为 cur_edge，如果 dis[u]+cue_edge的长度=dis[cur_edge的终点]，那么显然这条边应该珂以是最短路树上的一条边，然后打一个标记表示cur_edge的终点不能再被加边了，题目要求字典序最小，显然u从1到n枚举珂以解决问题。
建好树以后跑一边DFS，我们知道当前节点u上连边的贡献是(dis[u] - t)×以u为根的子树的牛的个数，找到贡献最大的点更新答案即可。