最小生成树：Kruskal 与 Prim

// 标准答案 —— 枚举**所有边的子集**，从中挑出「是生成树」的那些，取权值和最小的
//
// 输入：第一行 n m
//       接下来 m 行 `u v w`，表示一条连接 u、v 的**无向**边，权值 w（⚠ **w 可以是负数**，|w| ≤ 100）
//       ⚠ 可能有重边、自环，也**不保证连通**
// 输出：最小生成树的权值和；如果整张图不连通（生成树根本不存在），输出一行 `IMPOSSIBLE`
//
// ⚠ 为什么「不连通」用 IMPOSSIBLE 而不是 -1：这一章的边权**可以是负数**，
//   权值和完全可能正好等于 -1。**答案的记号和数据的取值范围是一对** ——
//   第 33 章刚踩过一次（那一章走不到的点不能再用 -1，改成了 x），这是第二次。
//
// ★ 为什么标准答案要用一个和贪心毫无关系的思路写：
//   kruskal.cpp 和 prim.cpp 都是**贪心**，而且是同一条性质（切割性质）的两个推论 ——
//   拿它们互相验，只能验出「两处打字错误不一样」，验不出「那条性质本身是不是被我理解错了」。
//   这一份直接照着**定义**做：生成树 = 选出 n−1 条边、且所有点连通。
//   （第 9 章用 DP 验贪心、第 15 章用迭代加深验 BFS，都是这个道理。）
//
// ★ 「一个集合就是一个整数」第三次登场（第 3 章二进制枚举 → 第 28 章状压 DP → 这里）：
//   m 条边就是 m 个二进制位，枚举 0 .. 2^m−1 就枚举完了所有选法。
//   复杂度 O(2^m × n α)，所以对拍的数据里 m 必须很小（生成器把 m 压在 14 条以内）。
//
// ⚠ 一个容易漏的地方：n == 1 时生成树是「一条边都不要」，答案是 0（而不是 IMPOSSIBLE）。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> fa;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);
    for (auto& e : es) cin >> e[0] >> e[1] >> e[2];

    const long long NONE = LLONG_MAX;
    long long best = NONE;

    // ⚠ 用 long long 数这个循环变量：m 到 31 时 `1 << m` 就溢出了。
    //   这本身就是「暴力只能当标准答案」的一部分 —— 边数刚过三十，它连**数都数不完**。
    for (long long S = 0; S < (1LL << m); S++) {
        if (__builtin_popcountll((unsigned long long)S) != n - 1) continue;   // 生成树恰好 n−1 条边
        fa.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) fa[i] = i;
        long long sum = 0;
        int comp = n;                                      // 还剩几个连通块
        for (int i = 0; i < m; i++)
            if (S >> i & 1) {
                sum += es[i][2];
                int a = find(es[i][0]), b = find(es[i][1]);
                if (a != b) { fa[a] = b; comp--; }         // ⚠ 自环 / 重边会让 comp 减不下去
            }
        if (comp != 1) continue;                           // 不连通 —— 那它就不是生成树
        if (best == NONE || sum < best) best = sum;
    }

    if (best == NONE) cout << "IMPOSSIBLE\n";
    else cout << best << "\n";
    return 0;
}

// 正解之一 —— Kruskal：把边按权值从小到大排，能连就连
//
// ★ 它为什么对，只有一句话（本章的关键一步）：**切割性质**。
//
//     把点集任意分成两半（S 和 V∖S），**横跨这个分法的边里最小的那条，
//     一定属于某一棵最小生成树。**
//
//   Kruskal 每次拿出的那条边 (u, v)，如果两端还不在同一个连通块里，
//   那就以「u 所在的那个连通块」当 S —— 因为比它更小的边**都已经处理过了**，
//   而它们要么在块内、要么两端也不横跨这个 S。
//   于是它就是横跨 (S, V∖S) 的最小边 → 由切割性质，选它不会错。
//
// ★ 需要的唯一工具是**并查集**（第 36 章的正主，这里先用它最朴素的样子）：
//   它只回答一个问题 ——「这两个点现在是不是已经连在一起了？」
//     find(x)  ：x 所在集合的代表元（顺手做**路径压缩**，把一路上的点直接挂到根上）
//     unite(a,b)：把两个集合并成一个，成功返回 true（说明它们本来不连通）
//
// ⚠ 两处初学者最常写错的地方，正文第 6 步各有一份代码：
//   ① 比较时忘了 find，直接写 `if (fa[u] != fa[v])` —— fa[u] 只是「爸爸」，不是「祖宗」；
//   ② 合并时写 `fa[u] = v`，也一样，那只是把两个**点**挂起来，不是把两个**集合**并起来。
//
// ⚠ 自环和重边不用特殊处理：自环两端本来就同块，find 一比就自己被跳过了；
//   重边里更小的那条先被处理，之后那条更大的自然成环。
//   ★ 注意这一点和第 33 章正好相反：那一章**负的自环就是一个负环**，是灾难；
//     这一章负的自环完全无害 —— 它一个新点都连不上，白送的负权拿不到。
//     （正文第 4 步那个 wrongNeg.cpp 就是没想明白这件事。）
//
// ★ 边权是负数也完全不影响：切割性质的证明里，**「w ≥ 0」这个条件一次都没用到**。
//   对照第 32 章：Dijkstra 的证明里非负性恰好用在一个不等号上，负权一来就断。
//   同一个「贪心」，一个怕负权、一个不怕 —— 差别在证明里看得清清楚楚。
//
// 复杂度 O(m log m)（瓶颈是排序）。

#include <bits/stdc++.h>
using namespace std;

vector<int> fa;

// 路径压缩：回来的路上，把这一路的点全部直接挂到根上
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

// ⚠ 一定是 fa[find(a)] = find(b)，把两个**根**接起来
bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;                 // 本来就连通 —— 再连就成环了
    fa[a] = b;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);              // (w, u, v) —— 权值放在最前面，直接 sort 就是按权排
    for (auto& e : es) cin >> e[1] >> e[2] >> e[0];
    sort(es.begin(), es.end());               // ★ 从小到大。反过来排就是「最大生成树」，见 wrongSort.cpp

    fa.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long ans = 0;
    int cnt = 0;                              // 已经选中的边数
    for (auto& e : es)
        if (unite(e[1], e[2])) { ans += e[0]; cnt++; }

    // ★ 选够 n−1 条才是一棵树。少一条都说明图本来就不连通
    if (cnt != n - 1) cout << "IMPOSSIBLE\n";
    else cout << ans << "\n";
    return 0;
}

// 并查集小节的演示程序 —— Kruskal 唯一依赖的那个工具，到底在干什么
//
// 输入和 kruskal.cpp 一样。它把边按权值从小到大过一遍，每条边打印一行：
//   这条边的两端各自的**祖宗**是谁 → 合并还是跳过 → 合并之后 fa 数组长什么样
// 并且**同时跑一份「不 find、直接比 fa」的错误写法**，把两者结论不同的那些行标出来。
//
// ★ 并查集只回答一个问题：「这两个点现在是不是已经连在一起了？」
//   它的实现是一片森林：fa[x] 是 x 的**爸爸**，一路往上走到头就是这一族的**祖宗**。
//
//     find(x)  ：一路往上找到祖宗。⚠ 回来的路上顺手**路径压缩** ——
//                把这一路的点全部直接挂到祖宗身上，下次就一步到位。
//     unite(a,b)：fa[find(a)] = find(b)，把两族的**祖宗**接起来。
//
// ★ 初学者最容易写错的就是这两句里的 find：
//     ✗ `if (fa[u] != fa[v])`  —— 比的是「爸爸」，不是「祖宗」。两个点的爸爸不同，
//                                 完全可能爷爷是同一个 —— 于是它以为不连通，把边收下，成了环。
//     ✗ `fa[u] = v`            —— 只把两个**点**挂了起来，u 那一族的其它人没跟着过去。
//   下面这张表就是拿来看这件事的：**「一样」那一列出现「不」的那一行，就是 bug 现场。**
//   （对应正文第 6 步的 wrongFa.cpp。）
//
// ⚠ 输出全部用 printf，含中文的列按显示宽度补空格（第 25、26 章那条：setw 数的是字节）。

#include <bits/stdc++.h>
using namespace std;

// 按显示宽度补空格：ASCII 算 1 格，非 ASCII（这里只有汉字）算 2 格
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;               // UTF-8 续字节，不算宽度
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

int n, m;
vector<int> fa, bad;                                    // fa：正确写法；bad：不 find 的错误写法

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

static string faLine(const vector<int>& f) {
    string s;
    for (int i = 1; i <= n; i++) s += to_string(f[i]) + (i == n ? "" : " ");
    return s;
}

int main() {
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);
    for (auto& e : es) cin >> e[1] >> e[2] >> e[0];      // (w, u, v)
    sort(es.begin(), es.end());

    fa.assign(n + 1, 0);
    bad.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = bad[i] = i;

    printf("按权值从小到大处理每一条边（fa[x] = x 的爸爸，一路往上走到头才是祖宗）\n\n");
    printf("  %s  %s  %s  %s  %s\n",
           padDisp("边", 10).c_str(), padDisp("find(u) find(v)", 17).c_str(),
           padDisp("正确写法", 14).c_str(), padDisp("不 find 直接比 fa", 20).c_str(),
           padDisp("一样", 6).c_str());
    printf("  %s  %s  %s  %s  %s\n", string(10, '-').c_str(), string(17, '-').c_str(),
           string(14, '-').c_str(), string(20, '-').c_str(), string(6, '-').c_str());

    long long ans = 0, ansBad = 0;
    int cnt = 0, cntBad = 0, diff = 0;
    for (auto& e : es) {
        int u = e[1], v = e[2], w = e[0];
        int a = find(u), b = find(v);
        bool takeOk = (a != b);
        if (takeOk) { fa[a] = b; ans += w; cnt++; }

        bool takeBad = (bad[u] != bad[v]);               // ✗ 只比爸爸
        if (takeBad) { bad[u] = bad[v]; ansBad += w; cntBad++; }   // ✗ 只挂点

        if (takeOk != takeBad) diff++;
        char edge[32], roots[32];
        snprintf(edge, sizeof(edge), "%d-%d(%d)", u, v, w);
        snprintf(roots, sizeof(roots), "%d %d", a, b);
        printf("  %s  %s  %s  %s  %s\n",
               padDisp(edge, 10).c_str(), padDisp(roots, 17).c_str(),
               padDisp(takeOk ? "收下" : "跳过（成环）", 14).c_str(),
               padDisp(takeBad ? "收下" : "跳过（成环）", 20).c_str(),
               padDisp(takeOk == takeBad ? "是" : "★ 不", 6).c_str());
    }

    printf("\n  fa 数组最后长这样：%s\n", faLine(fa).c_str());
    printf("  ★ 路径压缩之后，大多数点都被直接挂到了祖宗身上 —— 下次 find 一步到位。\n\n");
    printf("  正确写法：收了 %d 条边，权值和 %lld（要 %d 条才是一棵树）\n", cnt, ans, n - 1);
    printf("  不 find ：收了 %d 条边，权值和 %lld\n", cntBad, ansBad);
    if (diff) printf("  ★ 两者在 %d 条边上给出了不同的结论 —— 那几行就是 bug 现场。\n", diff);
    else printf("  这张图上两者恰好一致 —— ⚠ 不代表那个写法是对的，只代表这组数据没打中它。\n");
    return 0;
}

// 正解之二 —— Prim：从一个点开始，让树一点一点长大
//
// ★ 它和 kruskal.cpp 是**同一条性质**的两个推论，只是「选哪个切割」不一样：
//     Kruskal：切割由「当前这条边左端所在的连通块」定 —— 到处开花，最后连成一棵；
//     Prim：  切割永远是「已经长进树里的那堆点 S」和外面 —— 只有一棵树，一直在长。
//   每一步都取**横跨切割的最小边**，切割性质保证这一步不会错。
//
// ★★ 这一份和第 32 章的 naive.cpp（朴素 Dijkstra）**只差一个字**，值得并排看：
//
//     Dijkstra： if (dist[u] + g[u][v] < dist[v]) dist[v] = dist[u] + g[u][v];
//     Prim：     if (          g[u][v] < key[v] ) key[v]  =           g[u][v];
//                      ↑ 少了「dist[u] +」这一截
//
//   一句话解释这个差别：
//     Dijkstra 的 dist[v] 记的是「**从起点走到 v** 有多远」——   所以要一路累加；
//     Prim 的 key[v] 记的是「**从树上够到 v** 要花多少」——      只看那一条边。
//
//   ★ 而这个差别正好解释了另一件事：**为什么 Prim 不怕负权，Dijkstra 怕。**
//     Dijkstra 的贪心要「路越走越长」才成立（负权一来就断，第 32 章那个反证的第三句）；
//     Prim 压根不累加，切割性质的证明里一次都没用到 w ≥ 0。
//     ⚠ 所以这一章的对拍数据里**必须有负权边** —— 它验的就是这句话。
//     把 Prim 手滑写成 Dijkstra 就是 wrongDij.cpp，正文第 7 步专门讲。
//
// ⚠ 不连通怎么办：某一轮所有还在外面的点 key 都是 INF（谁都够不着），
//   说明剩下的点和树之间一条边都没有 —— 直接 IMPOSSIBLE。
//   ★ 这比 Kruskal 那句 `cnt != n-1` 早，但说的是同一件事。
//
// 复杂度 O(n²)（每轮扫一遍找最小）。稠密图上它不怕 m 大 —— 因为它压根不看 m。
// 堆优化的版本见 primHeap.cpp（那一份是把第 32 章的 fast.cpp 改一个字改出来的）。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    // 邻接矩阵，重边取 min（自环留着也没关系：轮到 u 时它早就在树里了）
    vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min(g[u][v], w);
        g[v][u] = min(g[v][u], w);            // ⚠ 无向图，两个方向都要存
    }

    vector<int> key(n + 1, INF);
    vector<char> in(n + 1, 0);
    key[1] = 0;                               // 从 1 号开始长。★ 从谁开始都行，见 primAny.cpp

    long long ans = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int v = 1; v <= n; v++)          // 找「外面的点里，够得最便宜的那个」
            if (!in[v] && (u == -1 || key[v] < key[u])) u = v;
        if (key[u] >= INF) { cout << "IMPOSSIBLE\n"; return 0; }   // 谁都够不着 → 不连通
        in[u] = 1;
        ans += key[u];                        // 把「够到它的那条边」的权计进去（第一轮加的是 0）
        for (int v = 1; v <= n; v++)
            if (!in[v] && g[u][v] < key[v]) key[v] = g[u][v];      // ★ 就是这一行，没有 key[u] +
    }

    cout << ans << "\n";
    return 0;
}

// ✗ 错误版本⑤：把 Prim 手滑写成了 Dijkstra
//
//     ✓ Prim：     if (          g[u][v] < key[v]) key[v] =           g[u][v];
//     ✗ 这一份：   if (key[u] + g[u][v] < key[v]) key[v] = key[u] + g[u][v];
//                        ↑ 多了「key[u] +」这一截
//
// ★ 一个字之差，它算的就成了**最短路径树**（从 1 号出发的那棵）——
//   一棵完全合法、但通常**不是最小**的生成树。
//   ⚠ 所以这一份的答案里，`ans` 我特意加的是「真正用到的那条边的权」，而不是 key[u]，
//     否则它连「一棵树的权值和」都不是了 —— 那样错得太明显，反而没有教学价值。
//     ★ 这个版本的意思是：**它给出的是一棵真的树，只是选错了那棵。**
//
// ★ 顺带把第 32 章那笔账翻出来对照：
//     Dijkstra 的贪心要「路越走越长」才成立 —— 负权一来就断（那一章那个反证的第三句）；
//     Prim 压根不累加，切割性质的证明里一次都没用到 w ≥ 0 —— 负权对它毫无影响。
//   所以这一份**顺手把「怕负权」这个毛病也一起带了回来**：它在负权数据上还会额外错一批。
//
// ⚠ 内层那句里特意补上了 `g[u][v] < INF`（「不是一条边就别算」）。
//   不补的话，有负权时 `key[u] + INF` 会比 INF **小**，于是「够不着」也被刷成一个数 ——
//   那正是第 33 章 wrongInf.cpp 那个坑。★ **错误版本也要干净：一份只错一件事。**
//   两个 bug 混在一份代码里，量出来的抓获率就说不清是谁的功劳了。
//
// ⚠ 它也是「答案不唯一」那件事的一块试金石：最短路径树和最小生成树**权值和不同**，
//   所以主对拍（只比一个数）抓得住它；要是当初图省事去比「选了哪些边」，
//   那就会连正确的 Prim 都一起判红。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = min(g[u][v], w);
        g[v][u] = min(g[v][u], w);
    }

    vector<int> key(n + 1, INF), from(n + 1, 0);   // from[v] = 把 v 够进来的那条边的权
    vector<char> in(n + 1, 0);
    key[1] = 0;

    long long ans = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int v = 1; v <= n; v++)
            if (!in[v] && (u == -1 || key[v] < key[u])) u = v;
        if (key[u] >= INF) { cout << "IMPOSSIBLE\n"; return 0; }
        in[u] = 1;
        ans += from[u];                            // 加的是边权（第一轮 from[1] = 0）
        for (int v = 1; v <= n; v++)
            if (!in[v] && g[u][v] < INF && key[u] + g[u][v] < key[v]) {   // ✗ 累加了 —— 这就成了 Dijkstra
                key[v] = key[u] + g[u][v];
                from[v] = g[u][v];
            }
    }

    cout << ans << "\n";
    return 0;
}

// ✗ 错误版本③：忘了检查「到底选够 n−1 条没有」
//
// 和 kruskal.cpp 只差最后那一句 `if (cnt != n - 1)`。
//
// ★ 它错在**题面**上，不在算法上：图不连通的时候，Kruskal 照样跑得欢 ——
//   它长出来的是一片**最小生成森林**，每个连通块里各一棵。
//   把那片森林的权值和当答案报出去，一点异常都没有：不崩溃、不越界、数还挺像话。
//
// ⚠ 所以它是**只有「不保证连通」这句话进了题面才存在的 bug** ——
//   而生成器要是「顺手保证图连通」（第 30 章那条），它就 0 / 300。
//   本章生成器的档位 1 干的就是这件事，正文第 9 步那张表第一行。

#include <bits/stdc++.h>
using namespace std;

vector<int> fa;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    fa[a] = b;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);
    for (auto& e : es) cin >> e[1] >> e[2] >> e[0];
    sort(es.begin(), es.end());
    fa.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long ans = 0;
    for (auto& e : es)
        if (unite(e[1], e[2])) ans += e[0];

    cout << ans << "\n";                      // ✗ 不管选够没有，直接报
    return 0;
}

// ✗ 错误版本④：「负权边是白送的，先全收了再说」
//
// 这是一个**看起来很有道理**的错误直觉：既然总权值要最小，那负的边当然是能拿就拿。
//
// ★ 它错在哪：生成树的限制不是「权值最小」四个字，还有前半句 ——
//   **必须恰好是一棵树**（n−1 条边、不成环）。负权边照样会凑成环，凑成环就不能全要。
//   ⚠ 最刺眼的一种情况是**负的自环**：它一个新点都连不上，那点「白送的负权」根本拿不到。
//     （对照第 33 章：那一章负的自环就是一个负环，是灾难；这一章它完全无害 ——
//      同一样东西在两章里的分量完全不同。）
//
// ★ 这个 bug 对生成器提出了一个很具体的要求：数据里得有**负权边凑出来的环**
//   （或者负的自环）。全是正权的数据上它和正解一模一样 —— 生成器的档位 2 就是干这个的。
//
// ⚠ 注意它「无脑收下」的那部分连 cnt 都算不准，所以症状同样可能是 IMPOSSIBLE。

#include <bits/stdc++.h>
using namespace std;

vector<int> fa;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    fa[a] = b;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);
    for (auto& e : es) cin >> e[1] >> e[2] >> e[0];
    fa.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long ans = 0;
    int cnt = 0;
    for (auto& e : es)
        if (e[0] < 0) {                       // ✗ 负的先无脑收下（连自环也收）
            ans += e[0];
            if (unite(e[1], e[2])) cnt++;
        }

    sort(es.begin(), es.end());
    for (auto& e : es)
        if (e[0] >= 0 && unite(e[1], e[2])) { ans += e[0]; cnt++; }

    if (cnt != n - 1) cout << "IMPOSSIBLE\n";
    else cout << ans << "\n";
    return 0;
}

// 不只报一个数，而是**把两种算法各自选中的那 n−1 条边都打印出来**
//
// 输入和 kruskal.cpp 一样。输出：
//   第一行：权值和（不连通就只有一行 IMPOSSIBLE）
//   然后 `KRUSKAL` + n−1 行 `u v w`：Kruskal 选中的边（按它选中的顺序）
//   然后 `PRIM`    + n−1 行 `u v w`：Prim 从 1 号点开始长出来的边（按它选中的顺序）
//
// ★ 为什么要有这一份（本章第二个关键点）：
//   **最小生成树可能不唯一，但权值和唯一。** 边权有并列时，两份都正确的程序
//   会长出**形状不同的树** —— 拿「选了哪些边」去逐字节对拍，立刻红一片，可谁都没错。
//   这是第 31 章「答案不唯一」的第二次登场，那一章给的两条出路，这一章两条都用上了：
//
//     ① **把答案钉唯一**：这道题天生就有一个唯一的东西 —— **权值和**。
//        题面只要那一个数，主对拍就能逐字节比。
//        （第 31 章是靠给题面加一句「输出字典序最小的那个」才钉住的，这一章白送。）
//     ② **写验证器**：不比答案，比性质。check:viz 拿到这两棵树之后各查四件事 ——
//        · 恰好 n−1 条边；
//        · 每一条都真的是原图里的边（不许凭空造边）；
//        · 连起来之后所有点连通（n−1 条边 + 连通 ⇔ 是一棵树）；
//        · 权值和等于第一行，也等于 brute.cpp 枚举出来的最小值。
//
//   ⚠ 第 31 章那个盲区在这里还在：**验证器证明不了「答案存在时你没漏报」** ——
//     一份永远输出 IMPOSSIBLE 的程序能通过所有合法性检查。
//     所以「不连通」这一支必须靠主对拍单独对。
//
// ★ 正文第 8 步把这两棵树并排画了出来：**在默认那张图上它们真的不一样**
//   （Kruskal 用 2−5，Prim 用 3−4，两条边权值都是 5），而权值和都是 9。
//   第 27、28 章那句「一份方案能自证清白，一个数字不能」第三次登场 ——
//   ⚠ 只不过这一次要反过来用：**能自证清白的是「它是不是一棵合法的生成树」，
//     而「它是不是最小的」还是只能靠那个数字。**

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

vector<int> fa;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);                        // (w, u, v)
    for (auto& e : es) cin >> e[1] >> e[2] >> e[0];

    /* ---------- Kruskal ---------- */
    vector<array<int, 3>> sorted = es;
    sort(sorted.begin(), sorted.end());
    fa.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;
    long long sumK = 0;
    vector<array<int, 3>> pickK;
    for (auto& e : sorted) {
        int a = find(e[1]), b = find(e[2]);
        if (a == b) continue;
        fa[a] = b;
        sumK += e[0];
        pickK.push_back({e[1], e[2], e[0]});
    }
    if ((int)pickK.size() != n - 1) { cout << "IMPOSSIBLE\n"; return 0; }

    /* ---------- Prim（从 1 号开始）---------- */
    vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));
    for (auto& e : es) {
        g[e[1]][e[2]] = min(g[e[1]][e[2]], e[0]);
        g[e[2]][e[1]] = min(g[e[2]][e[1]], e[0]);
    }
    vector<int> key(n + 1, INF), pre(n + 1, 0);         // pre[v] = 把 v 够进来的那个点
    vector<char> in(n + 1, 0);
    key[1] = 0;
    long long sumP = 0;
    vector<array<int, 3>> pickP;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int v = 1; v <= n; v++)
            if (!in[v] && (u == -1 || key[v] < key[u])) u = v;
        in[u] = 1;
        if (pre[u]) { sumP += key[u]; pickP.push_back({pre[u], u, key[u]}); }
        for (int v = 1; v <= n; v++)
            if (!in[v] && g[u][v] < key[v]) { key[v] = g[u][v]; pre[v] = u; }
    }

    cout << sumK << "\n";
    cout << "KRUSKAL\n";
    for (auto& e : pickK) cout << e[0] << " " << e[1] << " " << e[2] << "\n";
    cout << "PRIM\n";
    for (auto& e : pickP) cout << e[0] << " " << e[1] << " " << e[2] << "\n";
    // ⚠ 两个和必须相等 —— 不等就是这一章最核心的那句话出了问题
    if (sumK != sumP) cout << "★ 两个权值和居然不一样：" << sumK << " vs " << sumP << "\n";
    return 0;
}

// 正解之一 —— Kruskal：把边按权值从小到大排，能连就连
//
// ★ 它为什么对，只有一句话（本章的关键一步）：**切割性质**。
//
//     把点集任意分成两半（S 和 V∖S），**横跨这个分法的边里最小的那条，
//     一定属于某一棵最小生成树。**
//
//   Kruskal 每次拿出的那条边 (u, v)，如果两端还不在同一个连通块里，
//   那就以「u 所在的那个连通块」当 S —— 因为比它更小的边**都已经处理过了**，
//   而它们要么在块内、要么两端也不横跨这个 S。
//   于是它就是横跨 (S, V∖S) 的最小边 → 由切割性质，选它不会错。
//
// ★ 需要的唯一工具是**并查集**（第 36 章的正主，这里先用它最朴素的样子）：
//   它只回答一个问题 ——「这两个点现在是不是已经连在一起了？」
//     find(x)  ：x 所在集合的代表元（顺手做**路径压缩**，把一路上的点直接挂到根上）
//     unite(a,b)：把两个集合并成一个，成功返回 true（说明它们本来不连通）
//
// ⚠ 两处初学者最常写错的地方，正文第 6 步各有一份代码：
//   ① 比较时忘了 find，直接写 `if (fa[u] != fa[v])` —— fa[u] 只是「爸爸」，不是「祖宗」；
//   ② 合并时写 `fa[u] = v`，也一样，那只是把两个**点**挂起来，不是把两个**集合**并起来。
//
// ⚠ 自环和重边不用特殊处理：自环两端本来就同块，find 一比就自己被跳过了；
//   重边里更小的那条先被处理，之后那条更大的自然成环。
//   ★ 注意这一点和第 33 章正好相反：那一章**负的自环就是一个负环**，是灾难；
//     这一章负的自环完全无害 —— 它一个新点都连不上，白送的负权拿不到。
//     （正文第 4 步那个 wrongNeg.cpp 就是没想明白这件事。）
//
// ★ 边权是负数也完全不影响：切割性质的证明里，**「w ≥ 0」这个条件一次都没用到**。
//   对照第 32 章：Dijkstra 的证明里非负性恰好用在一个不等号上，负权一来就断。
//   同一个「贪心」，一个怕负权、一个不怕 —— 差别在证明里看得清清楚楚。
//
// 复杂度 O(m log m)（瓶颈是排序）。

#include <bits/stdc++.h>
using namespace std;

vector<int> fa;

// 路径压缩：回来的路上，把这一路的点全部直接挂到根上
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

// ⚠ 一定是 fa[find(a)] = find(b)，把两个**根**接起来
bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;                 // 本来就连通 —— 再连就成环了
    fa[a] = b;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);              // (w, u, v) —— 权值放在最前面，直接 sort 就是按权排
    for (auto& e : es) cin >> e[1] >> e[2] >> e[0];
    sort(es.begin(), es.end());               // ★ 从小到大。反过来排就是「最大生成树」，见 wrongSort.cpp

    fa.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;

    long long ans = 0;
    int cnt = 0;                              // 已经选中的边数
    for (auto& e : es)
        if (unite(e[1], e[2])) { ans += e[0]; cnt++; }

    // ★ 选够 n−1 条才是一棵树。少一条都说明图本来就不连通
    if (cnt != n - 1) cout << "IMPOSSIBLE\n";
    else cout << ans << "\n";
    return 0;
}

// 把三种写法的**工作量**数出来 —— 秒表只告诉你「谁快」，这个告诉你「为什么」
//
// 用法：./count       —— 读入一张图，报告三种写法各自的工作量
//       ./count io    —— ★ **只读入，什么都不算**，用来量「读入本身要多久」
//
// ⚠ 为什么非要有那个 `io` 开关（第 29 章那条：**量之前先确认「你量的就是它」**）：
//   稠密图上光是读入 450 万条边就要好几秒，三份程序的耗时里有一大半是同一笔读入开销。
//   不把它单独量出来，那张耗时表比的就不是算法，而是 cin。
//   （第 29 章量内存时也是这样：给程序加一个「只做要量的那部分」的开关才对得上公式。）
//
// 三个计数器分别是什么：
//   · Kruskal    ：排序后**扫到第几条边就选够 n−1 条了** ——
//                  ★ 后面那一大截边根本没用上，可它们**已经被排过序了**。
//                  这解释了 Kruskal 的常数：瓶颈在排序，不在并查集。
//   · 堆优化 Prim：**入堆次数**（第 32 章那个数的同款）——
//                  一条边只有「真的把某个点刷便宜了」才入堆，所以 m log n 是个很松的上界。
//   · 朴素 Prim  ：扫描次数恒等于 n²，**和 m 一点关系都没有** ——
//                  这正是它在稠密图上有机会的原因。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

vector<int> fa;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    bool ioOnly = (argc > 1 && string(argv[1]) == "io");

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<array<int, 3>> es(m);
    for (auto& e : es) cin >> e[1] >> e[2] >> e[0];       // (w, u, v)

    if (ioOnly) {                                          // ★ 只读入，立刻收工
        printf("只读入：%d 个点、%d 条边，什么都没算\n", n, m);
        return 0;
    }

    /* Kruskal：排序之后，扫到第几条边就选够了 */
    sort(es.begin(), es.end());
    fa.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) fa[i] = i;
    long long scanned = 0;
    int cnt = 0;
    for (auto& e : es) {
        scanned++;
        int a = find(e[1]), b = find(e[2]);
        if (a != b) { fa[a] = b; cnt++; }
        if (cnt == n - 1) break;
    }

    /* 堆优化 Prim：入堆次数 */
    vector<vector<pair<int, int>>> g(n + 1);
    for (auto& e : es) {
        g[e[1]].push_back({e[2], e[0]});
        g[e[2]].push_back({e[1], e[0]});
    }
    vector<int> key(n + 1, INF);
    vector<char> in(n + 1, 0);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    key[1] = 0;
    q.push({0, 1});
    long long pushes = 1;
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (in[u]) continue;
        in[u] = 1;
        for (auto [v, w] : g[u])
            if (!in[v] && w < key[v]) { key[v] = w; q.push({w, v}); pushes++; }
    }

    printf("这张图：%d 个点、%d 条边\n\n", n, m);
    printf("  Kruskal      ：排序 %d 条边，但只扫到第 %lld 条就选够 n−1 条了（%.1f%%）\n",
           m, scanned, m ? 100.0 * (double)scanned / m : 0.0);
    printf("  堆优化 Prim  ：入堆 %lld 次（边数的 %.1f%%）—— m log n 是个很松的上界\n",
           pushes, m ? 100.0 * (double)pushes / m : 0.0);
    printf("  朴素 Prim    ：扫描 %lld 次（= n²），和 m 一点关系都没有\n", (long long)n * n);
    printf("\n★ 稀疏图上 n² 远大于 m，稠密图上正好反过来 —— 选型就是在比这两个数。\n");
    return 0;
}