#include <bits/stdc++.h>

using namespace std;

class UnionFind{
public:
    vector<int> TT, RG;
    int n;
    UnionFind(int n) : TT(n+1, 0), RG(n+1, 0), n(n) {}
    bool equal(int x, int y){
        return find(x) == find(y);
    }
    int find(int x){
        int p = x, f;
        while(TT[p] != 0)
            p = TT[p];
        while(TT[x] != 0){ // Path compression
            f = TT[x];
            TT[x] = p;
            x = f;
        }
        return x;
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);

        if(x == y) //Nothing to do
            return;
        if(RG[x] > RG[y]) //Union by rank
            TT[y] = x;
        else if(RG[y] > RG[x])
            TT[x] = y;
        else{
            TT[y] = x;
            RG[x]++;
        }
    }
};

class MST{
public:
    vector<vector<pair<int, int> > > G;
    vector<tuple<int, int, int> > E;
    vector<pair<int,int> > F;
    UnionFind U;
    int n, m;
    long long cost = 0;
    MST(int n, int m, decltype(E)& Edges) : G(n+1), E(move(Edges)), U(n), n(n), m(m) {}

    void build(){
        int num = 0;
        int x, y, c;
        sort(E.begin(), E.end());
        for(auto it = E.begin(); it != E.end() and num < (n - 1); it++){
            tie(c, x, y) = *it;
            if(U.equal(x, y))
                continue;
            U.unite(x, y);
            G[x].emplace_back(y, c);
            G[y].emplace_back(x, c);
            F.emplace_back(x, y);
            cost += c;
        }
    }
};


int n, m;
vector<tuple<int, int, int> > E;
MST *M;

void Read()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    cin>>n>>m;
    int x, y, c;
    for(int i = 0; i < m; i++){
        cin>>x>>y>>c;
        E.emplace_back(c, x, y);
    }
}

void Solve()
{
    M = new MST(n, m, E);
    M->build();
}

void Print()
{
    cout<<M->cost<<"\n";
    cout<<n-1<<"\n";
    for(auto& it : M->F)
        cout<<get<0>(it)<<" "<<get<1>(it)<<"\n";
}

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

    Read();
    Solve();
    Print();
    return 0;
}