# 【題解】ZeroJudge b117: TOI2008 4. 地道問題

```#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 1000005;
int n, m, inf = 1e9, dis[maxn];
long long ans;
vector < pair<int, int> > out[maxn], in[maxn];

int main() {
while (cin >> n >> m){
for (int i = 1; i <= n; i++){
dis[i] = inf;
out[i].clear();
in[i].clear();
}
for (int i = 0, a, b, w; i < m; i++){
cin >> a >> b >> w;
out[a].push_back({b, w});
in[b].push_back({a, w});
}
ans = 0;
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push({0, 1});

dis[1] = 0;
while (!pq.empty()){
int x = pq.top().second, y = pq.top().first;
pq.pop();
if (dis[x] != y) continue;
ans += dis[x];
//cout << "1 -> " << x << " : " << dis[x] << "\n";
for (auto i:out[x]){
if (dis[i.first] > dis[x]+i.second){
dis[i.first] = dis[x]+i.second;
pq.push({dis[i.first], i.first});
}
}
}
//cout << ans << "\n";
pq.push({0, 1});
for (int i = 1; i <= n; i++){
dis[i] = inf;
}
dis[1] = 0;
while (!pq.empty()){
int x = pq.top().second, y = pq.top().first;
pq.pop();
if (dis[x] != y) continue;
ans += dis[x];
//cout << "1 <- " << x << " : " << dis[x] << "\n";
for (auto i:in[x]){
if (dis[i.first] > dis[x]+i.second){
dis[i.first] = dis[x]+i.second;
pq.push({dis[i.first], i.first});
}
}
}
cout << ans << "\n";
}
}
```