#include<bits/stdc++.h>
#define N 200030
#define pii pair<int,int>
#define x first
#define y second
using namespace std;

struct lol {
    int x, y,c;
    bool operator<(const lol &other) const {
        return c<other.c;
    }
};

int n,m,rs,k;
bool inA[N];
vector<pii>V[N];
int d[N],p[N];
multiset<lol>S;

void Prim() {
    inA[1]=1;
    for (int i=2; i<=n; ++i) d[i]=1e9;
    for (auto it:V[1]) {
        S.insert({1,it.x,it.y});
    }
    for (int i=1; i<n; ++i) {
        lol top;
        do {
            top=*S.begin();
            S.erase(S.begin());
        } while (inA[top.y]);
        int x=top.y;
        inA[x]=1;
        p[x]=top.x;
        rs+=top.c;
        for (auto it:V[x]) {
            if (!inA[it.x]) {
                S.insert({x,it.x,it.y});
            }
        }
    }
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int x,y,c; cin>>x>>y>>c;
        V[x].push_back({y,c});
        V[y].push_back({x,c});
    }
    Prim();
    cout<<rs<<'\n'<<n-1<<'\n';
    for (int i=1; i<=n; ++i) {
        if (p[i]) cout<<p[i]<<" "<<i<<'\n';
    }

    return 0;
}