Amy28 @ 2022-05-21 19:43:20
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
struct edge
{
int node;
int w;
edge(int node_,int w_):
node(node_),w(w_){}
};
const long long u=2000005;
vector<edge> v[u];
long long dis[u];
bool vis[u];
int n,m,s(1);
inline int read()
{
char ch=getchar();
register int x=0,f=1;
while(ch<'0' || ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(long long N)
{
if(N<0) putchar('-'),N=~(N-1);
register int s[20],top=0;
while(N) s[++top]=N%10,N/=10;
if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
putchar('\n');
}
inline void dijkstra()
{
__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> >,pairing_heap_tag> q;
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
pair<int,int> k=q.top();
q.pop();
if(vis[k.second]) continue;
vis[k.second]=1;
dis[k.second]=k.first;
for(vector<edge>::iterator i=v[k.second].begin();i!=v[k.second].end();i++)
{
q.push(make_pair(i->w+k.first,i->node));
}
}
}
int main()
{
long long ans(0);
n=read(),m=read();
for(int i(1);i<=m;i++)
{
register int x,y,w;
x=read(),y=read(),w=read();
v[x].push_back(edge(y,w));
v[y+n].push_back(edge(x+n,w));
}
dijkstra();
for(int i(2);i<=n;i++)
{
ans+=dis[i];
}
s=n+1;
dijkstra();
for(int i(n+2);i<=(n<<1);i++)
{
ans+=dis[i];
}
write(ans);
return 0;
}