Tankoldable @ 2017-08-21 20:23:05
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
long long n,m,tot,h1[1000005],h2[1000005],dis[1000005],u[1000005],ans;
struct cmp{
bool operator() (int a,int b)
{
return dis[a]>dis[b];
}
};
priority_queue<int ,vector<int>,cmp>q;
struct date{
long long si,len,ne;
}line[2000005];
int main()
{
cin>>n>>m;
long long a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
line[++tot].si=b;
line[tot].len=c;
line[tot].ne=h1[a];
h1[a]=tot;
line[++tot].si=a;
line[tot].len=c;
line[tot].ne=h2[b];
h2[b]=tot;
}
for(int i=1;i<=n;i++) dis[i]=200000000000000;
dis[1]=0;
q.push(1);
while(!q.empty())
{
int k=q.top();
q.pop();
if(u[k]) continue;
u[k]=1;
for(int i=h1[k];i;i=line[i].ne)
if(dis[k]+line[i].len<dis[line[i].si])
{
dis[line[i].si]=dis[k]+line[i].len;
q.push(line[i].si);
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
for(int i=1;i<=n;i++) dis[i]=200000000000000;
memset(u,0,sizeof(u));
dis[1]=0;
q.push(1);
while(!q.empty())
{
int k=q.top();
q.pop();
if(u[k]) continue;
u[k]=1;
for(int i=h2[k];i;i=line[i].ne)
if(dis[k]+line[i].len<dis[line[i].si])
{
dis[line[i].si]=dis[k]+line[i].len;
q.push(line[i].si);
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
printf("%lld",ans);
return 0;
}