两次dj，分别是正图反图

#include<bits/stdc++.h>
using namespace std;


int tu1[1010][1010],tu2[1010][1010];
int md[1010],n,m,u,v,w;
int book[1010],minn,mint;
int sum;


int main(){
	memset(tu1,0x3f,sizeof tu1);
	memset(tu2,0x3f,sizeof tu2);
	memset(md,0x3f,sizeof md);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		tu1[u][v]=w;//正图
		tu2[v][u]=w;//反图
	}
	for(int i=1;i<=n;i++){
		tu1[i][i]=tu2[i][i]=0;//对角线初始化
	}
	
	
	
	md[1]=0;//存最短路径
   //正图dj
	for(int i=1;i<=n;i++){
		md[i]=tu1[1][i];
	}
	book[1]=1;
	for(int i=1;i<n;i++){
		mint=0x3f3f3f3f;
		for(int j=1;j<=n;j++){
			if(md[j]<mint&&!book[j]){
				mint=md[j];
				minn=j;
			}
		}
		book[minn]=1;//标记,不会再更新
		for(int j=1;j<=n;j++){
			if(md[j]>md[minn]+tu1[minn][j]&&tu1[minn][j]!=0x3f3f3f3f){
				md[j]=md[minn]+tu1[minn][j];
			}
		}
	}
	
	
	for(int i=1;i<=n;i++){
		sum+=md[i];//sum存答案
	}
	
	
	
	//反图dj
	memset(md,0x3f,sizeof md);
	memset(book,0,sizeof book);
	md[1]=0;
	for(int i=1;i<=n;i++){
		md[i]=tu2[1][i];
	}
	book[1]=1;
	for(int i=1;i<n;i++){
		mint=0x3f3f3f3f;
		for(int j=1;j<=n;j++){
			if(md[j]<mint&&!book[j]){
				mint=md[j];
				minn=j;
			}
		}
		book[minn]=1;
		for(int j=1;j<=n;j++){
			if(md[j]>md[minn]+tu2[minn][j]&&tu2[minn][j]!=0x3f3f3f3f){
				md[j]=md[minn]+tu2[minn][j];
			}
		}
	}
	
	
	for(int i=1;i<=n;i++){
		sum+=md[i];
	}
	
	
	cout<<sum;
	return 0;
}