针对第一条题解的优化

为了以防超时，我们还可以像写最短路 $Dijkstra$ 算法时一样用堆优化的方法来写。
基本代码详情请见这里

接下来进行如下修改（详见下面代码的注释）：

#include<bits/stdc++.h>
using namespace std;
const int N=2025,MOD=1e9+7;
#define MAXN 0x7f7f7f7f
struct Node{
    int v,w;
    friend bool operator<(const Node&a,const Node&b){ //加入结构体自定义比较方式
        return a.w>b.w; //这样在优先队列中是小根堆
    }
};
priority_queue<Node>q; //使用优先队列来查找最小值，时间复杂度从O(n^2)降为O(nlog(n))
vector<Node>graph[N];
int n,m,u,v,w,ans;
int dist[N];
bool vis[N];
inline void read(int&x){
    bool nega=0;
    int res=0;
    char c=cin.get();
    while((c>'9'||c<'0')&&c!='-')c=cin.get();
    if(c=='-')nega=1;
    else res=c-'0';
    c=cin.get();
    while(c>='0'&&c<='9'){
        res=res*10+c-'0';
        c=cin.get();
    }
    if(nega)res*=-1;
    x=res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read(n);read(m);
    while(m--){
        read(u);read(v);read(w);
        graph[u].push_back({v,(w+MOD)%MOD});
        graph[v].push_back({u,(w+MOD)%MOD});
    }
    int u=1;
    for(int i=0;i<=n;i++)dist[i]=MAXN;
    dist[u]=0;
    q.push({u,0}); //加入队列
    while(q.size()){ //重复执行条件更改为队列中有元素
        Node f=q.top(); //取优先队列队首元素
        q.pop(); //记得及时弹出
        u=f.v; //取出编号
        vis[u]=1; //别忘了标记
        for(auto node:graph[u]){
            int v=node.v,w=node.w;
            if(!vis[v]&&w<dist[v]){ //这里必须加上!vis[v]，否则答案错误
            //例如存在边{2,3,1}，不加上!vis[v]会导致dist[2]=dist[3]=1，重复计算
                dist[v]=w; //更新
                q.push({v,w}); //加入队列
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            puts("impossible");
            return 0;
        }
        ans+=dist[i];
    }
    cout<<ans;
    return 0;
}