1 #include <iostream>
2 #include <queue>
3 #include <cstring>
4
5 using namespace std;
6
7 typedef long long LL;
8 typedef pair<int, int> PII;
9 typedef pair<int, PII> PIP;
10
11 const int N = 1000010;
12
13 int h[N], e[N], ne[N], idx;
14 int w[N], dist[N];
15 bool st[N];
16 PIP tmp[N];
17
18 int n, m;
19
20 void add(int a, int b, int c)
21 {
22 e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
23 }
24
25 void spfa()
26 {
27 memset(dist, 0x3f, sizeof dist);
28 dist[1] = 0;
29
30 queue<int> q;
31 st[1] = true;
32 q.push(1);
33
34 while (q.size())
35 {
36 int t = q.front();
37 q.pop();
38 st[t] = false;
39
40 for (int i = h[t]; i != -1; i = ne[i])
41 {
42 int j = e[i];
43
44 if (dist[j] > dist[t] + w[i])
45 {
46 dist[j] = dist[t] + w[i];
47 if (!st[j])
48 {
49 st[j] = true;
50 q.push(j);
51 }
52 }
53 }
54 }
55 }
56
57 int main()
58 {
59 ios::sync_with_stdio(0);
60 cin.tie(0);
61
62 cin >> n >> m;
63
64 for(int i = 0; i < m; i ++ )
65 {
66 int a, b, c;
67 cin >> a >> b >> c;
68 tmp[i] = {a, {b, c}};
69 }
70
71 memset(h, -1, sizeof h);
72 for (int i = 0; i < m; i ++ ) add(tmp[i].first, tmp[i].second.first, tmp[i].second.second);
73
74 spfa();
75
76 LL sum = 0;
77 for (int i = 1; i <= n; i ++ ) sum += dist[i];
78
79 memset(h, -1, sizeof h);
80 memset(st, 0, sizeof st);
81 idx = 0;
82
83 for (int i = 0; i < m; i ++) add(tmp[i].second.first, tmp[i].first, tmp[i].second.second);
84
85 spfa();
86
87 for (int i = 1; i <= n; i ++ ) sum += dist[i];
88
89 cout << sum;
90 }
