#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int nMax = 200003;
const int mMax = 300000;
bool used[mMax];
struct Grf{
    int from, to, cost;
};
struct cmp{
    inline bool operator ()(const Grf A,const Grf B)
    {
        return A.cost>B.cost;
    }
};
vector < Grf > Graf[nMax];
vector < Grf > Sol;
priority_queue < Grf, vector <Grf> , cmp > Heap;
int ans;
inline void Prim() {
    while(!Heap.empty()) {
        Grf edge = Heap.top();
        Heap.pop();
        if(used[edge.to]) {
            continue;
        }
        ans += edge.cost;
        Sol.push_back(edge);
        used[edge.from] = 1;
        used[edge.to]  = 1;
        for(auto next : Graf[edge.to]) {
            if(!used[next.to]) {
                Heap.push(next);
            }
        }
    }
}
int main()
{
    Grf init;
    int n , m, x, y ,c;
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        f>> x >> y >> c;
        init.from = x;
        init.to = y;
        init.cost = c;
        Graf[x].push_back(init);
        init.from = y;
        init.to = x;
        Graf[y].push_back(init);
    }
    for(auto i : Graf[1]) {
        Heap.push(i);
    }
    Prim();
    g<< ans << " " << n - 1 <<"\n";
    for(auto i : Sol) {
        g<< i.from << " " << i.to <<"\n";
    }
    return 0;
}