// 自己写的代码在第一次提交了里面
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 104;

struct edge{
    int u, v, c;
    bool operator< (const edge &w) const{
        return c < w.c;
    }
}e[204];
int p[N], n, m, k;
int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int kl(){
    int res = 0;
    for (int i = 0; i < k; i ++){
        int a = find(e[i].u), b = find(e[i].v), c = e[i].c;
        // 如果不是一个并查集就加入进去
        if (a != b) p[a] = b;
        else res += c;
    }
    return res;
}
int main(){
    cin >> n >> m;

    for (int i = 0; i <= n; i ++) p[i] = i;
    int a, b, c;
    while (m --){
        cin >> a >> b >> c;
        if (!c) continue;
        e[k ++] = {a, b, c};
    }
    sort (e,e + k);

    cout << kl() << endl;

    return 0;
}

// prime算法模板题
#include <iostream>
#include <cstring>
using namespace std;
const int N = 105;
int n;
int g[N][N], dist[N];
bool st[N];
int prime(){
    memset (dist, 0x7f, sizeof dist);
    int res = 0;
    dist[1] = 0;
    for (int i = 1; i <= n; i ++){
        int minidx = -1;
        for (int j = 1; j <= n; j ++){
            if (!st[j] && (minidx == -1 || dist[minidx] > dist[j])){
                minidx = j;
            }
        }

        res += dist[minidx];
        st[minidx] = true;

        for (int j = 1; j <= n; j ++) dist[j] = min(dist[j], g[minidx][j]);
    }
    return res;
}
int main(){


    cin >> n;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            cin >> g[i][j];

    cout << prime() << endl;

    return 0;
}

// 离散化 + 快速幂 + 变种的Floyd

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int MAXN = 210;

int N, n, T, S, E;
int g[MAXN][MAXN];
int res[MAXN][MAXN];// res[N][i][j] = min (res[N][i][j], res[a][i][k] + res[b][k][j]); 表示a步从i - > k, b步从 k -> j,其中N = a + b;

void mul(int c[][MAXN], int a[][MAXN], int b[][MAXN]) {
static int temp[MAXN][MAXN];// 临时存放答案，不能用res存放
memset(temp, 0x3f, sizeof temp);
for (int k = 1; k <= n; k)
for (int i = 1; i <= n; i)
for (int j = 1; j <= n; j++)
temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
memcpy(c, temp, sizeof temp);
}

void qmi() {
memset(res, 0x3f, sizeof res);
for (int i = 1; i <= n; i++) res[i][i] = 0; // 这里没看懂
// 因为前面一段和后面一段互不影响，所以可以使用快速乘法
while (N) {
if (N & 1) mul(res, res, g); // res = res * g
mul(g, g, g); // g = g * g
N >>= 1;
}
}

int main() {
cin >> N >> T >> S >> E;

memset(g, 0x3f, sizeof g);
map<int, int> ids;
if (!ids.count(S)) ids[S] = ++n;
if (!ids.count(E)) ids[E] = ++n;
S = ids[S], E = ids[E];

while (T--) {
    int a, b, c;
    cin >> c >> a >> b;
    if (!ids.count(a)) ids[a] = ++n;
    if (!ids.count(b)) ids[b] = ++n;
    a = ids[a], b = ids[b];

    g[a][b] = g[b][a] = min(g[a][b], c);
}

qmi();

cout << res[S][E] << endl;

return 0;

}

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N], g[N][N];
int pos[N][N];// f[i][j]表示从i -> j经过的中间点
int path[N], cnt;// 存最小环的信息

void get_path(int u, int v) {
    // u和v中间没有其它的点了
    if (pos[u][v] == 0) return;

    int k = pos[u][v];
    get_path(u, k);
    path[cnt++] = k;
    get_path(k, v);
}

int main() {
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; i++) g[i][i] = 0;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);// 防止重边
    }

    int res = INF;
    memcpy(d, g, sizeof d);
    // 运用dp的分析思想，把每个环里面的最大点编号分为k类
    // 因为Floyd里面 i -> k -> j，中间点k,由i - > k 之后一定不会不回去（回去就相当于存在了负环），所以状态是二维
    // Floyd有dp和图论的两种性质
    for (int k = 1; k <= n; k++) {
        // 求最小环
        for (int i = 1; i < k; i++) {
            for (int j = i + 1; j < k; j++) {
                // 更新答案res 和方案，当前路径是i -> k -> j -> i
                if ((long long) d[i][j] + g[j][k] + g[k][i] < res) {
                    res = d[i][j] + g[j][k] + g[k][i];
                    cnt = 0;

                    path[cnt++] = i;
                    path[cnt++] = k;
                    path[cnt++] = j;
                    get_path(j, i);

                }
            }
        }
        // Floy求最短路，并记录转移的中间点
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    pos[i][j] = k;
                }
    }

    if (res == INF) puts("No solution.");
    else {
        // 输出的顺序不唯一
        for (int i = 0; i < cnt; i++) cout << path[i] << ' ';
        cout << endl;
    }

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 30;
int n, m;
bool g[N][N];
bool st[N];

void floyd() {

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] |= g[i][k] && g[k][j];

}

int check() {
    for (int i = 1; i <= n; i++)
        if (g[i][i])
            return 2;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (!g[i][j] && !g[j][i])
                return 0;


    return 1;
}

char get_min() {
    for (int i = 0; i < n; i++) {
        if (!st[i]) {
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (!st[j] && g[j][i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                st[i] = true;
                return 'A' + i;
            }
        }
    }
}

int main() {

    while (cin >> n >> m, n || m) {
        memset(g, 0, sizeof g);
        int type = 0, t = 0;// type 为0 表示不确定。为1表示确定，为表示冲突；1
        char str[5];
        for (int i = 1; i <= m; i++) {
            cin >> str;
            int a = str[0] - 'A', b = str[2] - 'A';

            if (!type) {
                g[a][b] = true;
                floyd();
                type = check();
                if (type) t = i;
            }

        }

        if (!type) puts("Sorted sequence cannot be determined.");
        else if (type == 2) printf("Inconsistency found after %d relations.\n", t);
        else {
            memset(st, 0, sizeof st);
            printf("Sorted sequence determined after %d relations: ", t);
            for (int i = 0; i < n; i++) cout << get_min();
            cout << '.' << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;
typedef pair<int, int> PII;
const int N = 155, INF = 2e9;
PII arr[N];
int n;
char g[N][N];
double dis[N][N], maxd[N];

double get(PII a, PII b) {
    int x = a.first - b.first, y = a.second - b.second;
    return sqrt(x * x + y * y);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i].first >> arr[i].second;
    for (int i = 0; i < n; i++) cin >> g[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                if (g[i][j] == '0') dis[i][j] = INF;
                else dis[i][j] = get(arr[i], arr[j]);
            }
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    // 判断是否连通不能使用 g[i][j] 来判断
    double res1 = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dis[i][j] < INF / 2)
                maxd[i] = max(maxd[i], dis[i][j]);
        }
        res1 = max(res1, maxd[i]);
    }

    double res2 = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dis[i][j] >= INF) {
                res2 = min(maxd[i] + maxd[j] + get(arr[i], arr[j]), res2);
            }
        }
    }
    printf("%.6lf\n", max(res1, res2));
    return 0;
}

````

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 1004, M = 20005;
int cases, n, m, a, b, l, S, F;
int head[N], Next[M], edge[M], ver[M], tot;
int dis[N][2], cnt[N][2];
bool st[N][2];

void add(int u, int v, int c) {
ver[++tot] = v, edge[tot] = c, Next[tot] = head[u], head[u] = tot;
}

struct Ver {
int dist, type, ID;

Ver(int dist, int type, int id) : dist(dist), type(type), ID(id) {}

bool operator> (const Ver &W) const {
    return dist < W.dist;
}

};

int dijkstra() {
memset(dis, 0x3f, sizeof dis);
memset(st, false, sizeof st);
memset(cnt, 0, sizeof cnt);
cnt[S][0] = 1, dis[S][0] = 0;

priority_queue<Ver> q;// 这里是小根堆，重载了< 符号
q.push(Ver(0, 0, S));

while (!q.empty()) {
    Ver t = q.top();
    q.pop();

    int id = t.ID, type = t.type, distance = t.dist, counts = cnt[id][type];

    if (st[id][type]) continue;
    st[id][type] = true;

    for (int i = head[id]; i; i = Next[i]) {
        int j = ver[i];
        // 核心代码：转移方法的计算
        if (dis[j][0] > distance + edge[i]) { // 比最小的大，那就把原先最小的赋值给次小的，并且次小的人队
            dis[j][1] = dis[j][0], cnt[j][1] = cnt[j][0];
            q.push(Ver(dis[j][1], 1, j));
            // 更新最小的入队
            dis[j][0] = distance + edge[i], cnt[j][0] = counts;
            q.push(Ver(dis[j][0], 0, j));
        } else if (dis[j][0] == distance + edge[i]) { //等于的话，可以由这个状态转移过来，加上去
            cnt[j][0] += counts;
        } else if (dis[j][1] > distance + edge[i]) {
            dis[j][1] = distance + edge[i], cnt[j][1] = counts;
            q.push(Ver(dis[j][1], 1, j));

        } else if (dis[j][1] == distance + edge[i]) {
            cnt[j][1] += counts;
        }

    }
}

int res = cnt[F][0];
if (dis[F][0] + 1 == dis[F][1]) res += cnt[F][1];

return res;

}

int main() {

cin >> cases;
while (cases--) {
    memset(head, 0, sizeof head), tot = 0;
    cin >> n >> m;
    while (m--) {
        cin >> a >> b >> l;
        add(a, b, l);
    }
    cin >> S >> F;
    cout << dijkstra() << endl;
}
return 0;

}
```

// 求最短路条数，要把图抽象成一种最短路树（拓扑图）。
// 求最短的算法有以下几种：
// 1. BFS 每个点只入队一次，出队一次。满足拓扑图
// 2. dijkstra 每个点只出队一次。满足拓扑图。
// 3. bellman_ford算法 spfa 不满足拓扑序，可以做但是很麻烦，做法：先求出所有的路径数，建立最短路径树，再在树上做拓扑排序
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e5 + 5, MOD = 100003, M = 4e5 + 5;
int head[N], ver[M], Next[M], tot;
int m, n;
int dis[N], cnt[N];

void add(int u, int v) {
    ver[++tot] = v, Next[tot] = head[u], head[u] = tot;
}

void bfs() {
    memset(dis, 0x7f, sizeof dis);
    dis[1] = 0, cnt[1] = 1;
    queue<int> q;
    q.push(1);
    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = head[t]; i; i = Next[i]) {
            int j = ver[i];
            if (dis[j] > dis[t] + 1) { // 第一次到达这个点 那么等于上一个点的数量 + 1
                dis[j] = dis[t] + 1;
                cnt[j] = cnt[t], q.push(j);
            } else if (dis[j] == dis[t] + 1) { // 是最小的值，应该加上去
                cnt[j] = (cnt[t] + cnt[j]) % MOD;
            }
        }

    }


}

int main() {
    cin >> n >> m;
    int a, b;
    while (m--) {
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs();
    for (int i = 1; i <= n; i++) cout << cnt[i] << endl;

    return 0;
}

// 双端队列优化版的dijkstra
#include <cstring>
#include <iostream>
#include <deque>
#include <set>

using namespace std;

typedef pair<int, int> PII;
// N 点数，M边数 = N * (N - 1) * 2 * 2，P钥匙的状态数，二进制
const int N = 11, M = 360, P = 1 << 10;

int n, m, k, p;
// 邻接表存储所有边,这里第一维的N * N 是因为把二维转化为了一维，第二维存储钥匙的状态
int head[N * N], ver[M], edge[M], Next[M], tot;
int g[N][N], key[N * N];// g存储的是每个点的顺序编号，key是每个编号（即位置）的钥匙状态
int dist[N * N][P]; // 这个状态的距离
bool st[N * N][P]; // 是否以出队

set<PII> edges;// 已经加入了哪些边

void add(int a, int b, int c) {
    ver[++tot] = b, edge[tot] = c, Next[tot] = head[a], head[a] = tot;
}

// 给没有说明类型的边建立边，即通道建立边
void build() {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    // 枚举所有边
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 枚举方向
            for (int u = 0; u < 4; u++) {
                int nx = i + dx[u], ny = j + dy[u];
                // 是否越界
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                int a = g[i][j], b = g[nx][ny];
                // 判断这条是否出现(是否在输入里面说明是什么边)
                if (!edges.count(make_pair(a, b)))
                    add(a, b, 0);
            }
        }
    }
}

int bfs() {
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    // first 是当前状态位置（编号），有二维转换为一维，second是当前钥匙状态
    deque<PII> q;
    q.push_back(make_pair(1, 0));

    while (!q.empty()) {
        PII t = q.front();
        q.pop_front();

        if (st[t.first][t.second]) continue;
        st[t.first][t.second] = true;
        // 第一次找到一到是最小值，返回即可。
        if (t.first == n * m) return dist[t.first][t.second];
        // 如果有钥匙，不管了就拿起来，因为没有什么花费
        if (key[t.first]) {
            int state = t.second | key[t.first];
            if (dist[t.first][state] > dist[t.first][t.second]) {
                dist[t.first][state] = dist[t.first][t.second];
                // 边权为0加入队头
                q.push_front(make_pair(t.first, state));
            }
        }

        for (int i = head[t.first]; i; i = Next[i]) {
            int j = ver[i];
            // 判断能否过去，编号要-1进行判断，&运算判断状态
            if (edge[i] && !(t.second >> (edge[i] - 1) & 1)) continue;   // 有门并且没有钥匙
            if (dist[j][t.second] > dist[t.first][t.second] + 1) {
                dist[j][t.second] = dist[t.first][t.second] + 1;
                // 边权为0加入队尾
                q.push_back(make_pair(j, t.second));
            }
        }
    }

    return -1;
}

int main() {
    cin >> n >> m >> p;
    // 给所有点编号，方便后面转换为一维
    for (int i = 1, t = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            g[i][j] = t++;

    int x1, y1, x2, y2, c;
    cin >> k;
    while (k--) {
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        int a = g[x1][y1], b = g[x2][y2];
        // 记录已经出现的边
        edges.insert(make_pair(a, b)), edges.insert(make_pair(b, a));
        // 如果不是墙是门，就建立一条无向边，是墙就不建立边
        if (c >= 1) add(a, b, c), add(b, a, c);
    }
    // 没有说的都建一条边,并设标志为0
    build();

    int s;
    cin >> s;
    while (s--) {
        cin >> x1 >> y1 >> c;
        // 编号 -1，减去偏移量，方便移位操作后判断
        c--, key[g[x1][y1]] |= 1 << c;
    }
    cout << bfs() << endl;

    return 0;
}

// 技巧：通过虚拟一个节点，把多源起点 到 多源终点 转换为虚拟节点出发到多终点的技巧
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;
const int N = 1003, M = 40010;
int arr[N];

int head[N], ver[M], Next[M], edge[M], tot;

void add(int u, int v, int c) {
    ver[++tot] = v, edge[tot] = c, Next[tot] = head[u], head[u] = tot;
}

bool st[N];
int dis[N];

void dijkstra(int u) {

    memset(dis, 0x3f, sizeof dis);
    memset(st, false, sizeof st);

    dis[u] = 0;
    priority_queue <pair<int, int>> q;
    q.push(make_pair(-dis[u], u));

    while (!q.empty()) {
        int t = q.top().second;
        q.pop();

        if (st[t]) continue;
        st[t] = true;

        for (int i = head[t]; i; i = Next[i]) {
            int j = ver[i];
            if (dis[j] > dis[t] + edge[i]) {
                dis[j] = dis[t] + edge[i];
                q.push(make_pair(-dis[j], j));
            }
        }
    }

}

int main() {
    int n, m, s;
    while (cin >> n >> m >> s) {
        int p, q, t;
        while (m--) {
            cin >> p >> q >> t;
            add(p, q, t);
        }

        int w, i = 1;
        cin >> w;

        while (w--) {
            cin >> arr[i];
            add(0, arr[i++], 0);
        }
        dijkstra(0);

        int res = dis[s] > 0x3f3f3f3f / 2 ? -1 : dis[s];
        cout << res << endl;

        tot = 0;
        memset(head, 0, sizeof head);
    }

    return 0;
}