#include<bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct edge {
    int x,y,cost;
};

struct edge_prim {
    int c,from,to;
    bool operator>(const edge_prim &other) const {
        return c > other.c;
    }
};

bool cmp(edge a, edge b) {
    return a.cost < b.cost;
}

struct DSU {
    vector<int> p, h;

    DSU(int n) {
        p.resize(n + 1);
        h.resize(n + 1);
        for (int i = 1 ; i <= n ; i ++) {
            p[i] = i;
            h[i] = 1;
        }
    }

    int Find(int x) {
        int r = x;
        while (p[r] != r) {
            r = p[r];
        }

        //actualizam toti copii la tatal lor este optimazare decat sa tot cauti din tata in fiu
        int y = x;
        while (y != r) {
            int aux = p[y];
            p[y] = r;
            y = aux;
        }

        return r;
    }

    void Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (h[x] < h[y]) {
            p[x] = y;
        }else {
            if (h[x] > h[y]) {
                p[y] = x;
            }else {
                p[x] = y;
                h[y] ++;
            }
        }
    }

};

void Kruskal(int n, int m) {
    DSU d(n);

    vector<edge> e;

    for (int i = 1 ; i <= m ; i ++) {
        int x,y,c;
        fin >> x >> y >> c;
        e.push_back({x,y,c});
    }
    int apm = 0 ;
    vector<edge> sol;
    // bool ok = false;
    // for (int i = 1 ; i <= 3 ; i++) {
    //     int x,y,c;
    //     fin >> x >> y >> c;
    //     if (d.Find(x) == d.Find(y)) {
    //         cout << "Nu exista";
    //         ok = true;
    //     }
    //     if (!ok) {
    //         d.Union(x,y);
    //         sol.push_back({x,y,c});
    //         apm += c;
    //     }
    // }
    //if (!ok) {
        sort(e.begin(),e.end(),cmp);

        for (auto i : e) {
            if (d.Find(i.x) != d.Find(i.y)) {
                d.Union(i.x,i.y);
                apm += i.cost;
                sol.push_back(i);
            }
        }

        fout << apm << '\n' << sol.size() << '\n';
       // sort(sol.begin(),sol.end(),cmp);
        for (auto it : sol) {
            fout << it.x << ' ' << it.y << '\n';
        }
    //}
}



void prim(int n, int m) {
    vector<vector<pair<int,int>>> adj(200005);
    vector<bool> vis(200005,0);
    vector<edge_prim> sol;
    priority_queue<edge_prim, vector<edge_prim>, greater<edge_prim>> pq;
    for (int i = 1; i <= m ; i ++) {
        int x,y,c;
        fin >> x >> y >> c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
        if (x == 1 || y == 1) {
            pq.push({c,min(x,y),max(x,y)});
            vis[1] = 1;
        }
    }
    int ans = 0;
    int cnt = 1;
    while (!pq.empty() && cnt < n) {
        edge_prim node = pq.top();
        pq.pop();
        if (!vis[node.to]) {
            for (auto i : adj[node.to]) {
                if (!vis[i.first]) {
                    pq.push({i.second,node.to,i.first});
                }
            }
            vis[node.to] = 1;
            ans += node.c;
            sol.push_back({node.c,node.from,node.to});
        }
    }
    fout <<ans << '\n'<< sol.size() << '\n';
    for (auto i : sol) {
        fout << i.from << " " << i.to << '\n';
    }
}

int main() {
    int n,m;
    fin >> n >> m;
    prim(n,m);
    return 0;
}