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

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

int minV() {
    int mn=0; d[mn]=1e9;
    for (int i=1; i<=n; ++i) {
        if (!inA[i] && d[i]<d[mn]) mn=i;
    }
    rs+=d[mn];
    return mn;
}

void PrimN2() {
    inA[1]=1;
    for (int i=2; i<=n; ++i) d[i]=1e9;
    for (auto it:V[1]) d[it.x]=it.y, p[it.x]=1;

    for (int i=1; i<n; ++i) {
        int x=minV();
        inA[x]=1;
        for (auto it:V[x]) {
            if (!inA[it.x] && d[it.x]>it.y) {
                d[it.x]=it.y;
                p[it.x]=x;
            }
        }
    }
}

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});
    }
    PrimN2();
    cout<<rs<<'\n'<<n-1<<'\n';
    for (int i=1; i<=n; ++i) {
        if (p[i]) cout<<p[i]<<" "<<i<<'\n';
    }

    return 0;
}