#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]++;
        }
    }
};

template <typename T>
struct MST{
    vector<vector<pair<int, int> > > G;
    vector<tuple<int, int, T> > E;
    vector<pair<int,int> > F;
    UnionFind *U;
    int n, m;
    T cost = 0;

    void addEdge(int x, int y, T cost){
        E.emplace_back(x, y, cost);
    }

    void setNM(int n, int m){
        this->n = n;
        this->m = m;
    }

    void build(){
        int num = 0;
        int x, y, c;
        sort(E.begin(), E.end(), [](tuple<int, int, int> t1, tuple<int, int, int> t2) -> bool {return get<2>(t1) < get<2>(t2);});
        G.resize(n+1);
        U = new UnionFind(n+1);
        for(auto it = E.begin(); it != E.end() and num < (n - 1); it++){
            tie(x, y, c) = *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;
        }
        delete U;
    }
};


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

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

void Solve()
{
    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;
}