思路：挺裸的最短路。
首先从(1)号站点到其他的站点的最小花费很容易想到单源最短路。
那么从其他站点返回(1)号站点的最小花费呢？从每个终点站点跑一遍Dijkstra吗？
不不不，首先从时间复杂度上就不对，时间复杂度基本上是(O(n^2logn))的，而我们的(n)为(1e6)，明显不可以。
我们考虑反向建边，从(1)号点跑两边Dijkstra。
为什么要反向建边，仔细想想，不难，我们从起点出发顺着边走可以到达其他点，那么我们把边反过来，再顺着走，不就相当于从其他点到起点吗。感性理解一下？？
啊实在不行照着下面的图自己手玩一遍？？这样更形象更具体。
画图来形象的理解一下qwq：
这是未反向建边的原图：
从(1)号点可以跑Dijkstra即可求出到其他点的最小花费。
反向建边后的图：
这个时候我们从(1)号点跑Dijkstra，所求出的到其他点的最小花费，不正是其他点返回(1)号点的最小花费嘛。
感觉反向建边是最短路和一些其他问题差不多都是图论问题？？中挺常用的思路的。
啊对还要注意开long long，不然会爆int。分析一下？
一共(1e6)条边，每条边的极限权值为(1e9)，来回一趟极限值差不多为(2e15)，而int的极限值为(2147483647)差不多是(2e9)，已经爆了int了。
其实我们应该养成理性分析的习惯，不要等OJ返回WA的时候才恍然大悟：哦，这道题要开long long！这句话才不是在说我呢qaq！！应该除了我没人犯这种错误吧orz。
代码：
#include <bits/stdc++.h>
using namespace std;
template<typename temp>void read(temp &x){
x = 0;temp f = 1;char ch;
while(!isdigit(ch = getchar())) (ch == '-') and (f = -1);
for(x = ch^48; isdigit(ch = getchar()); x = (x<<1)+(x<<3)+(ch^48));
x *= f;
}
template <typename temp, typename ...Args>void read(temp& a, Args& ...args){read(a), read(args...);}
const int maxn = 1e6+10;
int n, m;
long long ans, dis_to[maxn], dis_from[maxn], vis_to[maxn], vis_from[maxn];
vector<pair<int,int> > v_to[maxn], v_from[maxn];
void qwq(){return;}
void Dijkstra_to(){
memset(dis_to, 0x3f, sizeof(dis_to));
priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > >q;
q.push(make_pair(0,1));
dis_to[1] = 0;
while (q.size()){
int now = q.top().second, len = q.top().first;
q.pop();
if(vis_to[now]) continue;
vis_to[now] = 1;
for(int i = 0; i < v_to[now].size(); i ++){
int to = v_to[now][i].first, length = v_to[now][i].second;
if(dis_to[to] > len + length){
dis_to[to] = len + length;
q.push(make_pair(dis_to[to], to));
}
}
}
return qwq();
}
void Dijkstra_from(){
memset(dis_from, 0x3f, sizeof(dis_from));
priority_queue<pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > >q;
q.push(make_pair(0,1));
dis_from[1] = 0;
while (q.size()){
int now = q.top().second, len = q.top().first;
q.pop();
if(vis_from[now]) continue;
vis_from[now] = 1;
for(int i = 0; i < v_from[now].size(); i ++){
int to = v_from[now][i].first, length = v_from[now][i].second;
if(dis_from[to] > len + length){
dis_from[to] = len + length;
q.push(make_pair(dis_from[to], to));
}
}
}
return qwq();
}
signed main(){
read(n, m);
for(int i = 1, x, y, z; i <= m; i ++){
read(x, y, z);
v_to[x].push_back(make_pair(y,z));
v_from[y].push_back(make_pair(x,z));
}
Dijkstra_to();
Dijkstra_from();
for(int i = 1; i <= n; i ++) ans += dis_to[i]+dis_from[i];
printf("%lld", ans);
return 0;
}