/**
 * Author: Andu Scheusan (not_andu)
 * Created: 01.10.2023 08:32:20
*/

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define INFILE "apm.in"
#define OUTFILE "apm.out"

#define all(x) (x).begin(), (x).end()
#define MP make_pair
#define F first
#define S second

typedef long long ll;

struct DSU {
    vector<int> comp, sz;

    DSU (int n)
    {
        comp.resize(n + 1);
        sz.resize(n + 1, 1);
        for (int i = 1; i <= n; i++)
        {
            comp[i] = i;
        }
    }

    int find (int x)
    {
        if (comp[x] == x) return x;
        else return comp[x] = find(comp[x]);
    }

    void unite(int x, int y)
    {
        x = find(x), y = find(y);
        if (sz[x] < sz[y]) swap(x, y);
        if (x == y) return;
        comp[y] = x;
        sz[x] += sz[y];
    }
};

struct Edge{
    int x;
    int y;
    int cost;
};

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

int n, m;
ll cost = 0;
vector<Edge> edges;

void solve(){

    cin >> n >> m;

    DSU dsu(n);
    vector<pair<int, int> > ans;

    for(int i = 1; i <= m; ++i){

        Edge aux;
        int x, y, cost;

        cin >> x >> y >> cost;
        aux.x = x, aux.y = y, aux.cost = cost;

        edges.push_back(aux);

    }

    sort(edges.begin(), edges.end(), cmp);

    for(int i = 0; i < edges.size(); ++i){

        if(dsu.find(edges[i].x) != dsu.find(edges[i].y)){

            dsu.unite(edges[i].x, edges[i].y);

            cost += edges[i].cost;

            pair<int, int> aux;

            aux.first = edges[i].x, aux.second = edges[i].y;

            ans.push_back(aux);

        }

    }

    cout << cost << '\n';

    cout << ans.size() << '\n';

    for(int i = 0; i < ans.size(); ++i){

        cout << ans[i].second << " " << ans[i].first << '\n';

    }

}

int main(){
    
    ios_base::sync_with_stdio(false);

    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}