#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 p[N];
priority_queue<lol>S;

void Prim() {
    inA[1]=1;
    for (auto it:V[1]) {
        S.push({1,it.x,it.y});
    }
    for (int i=1; i<n; ++i) {
        lol top;
        do {
            top=S.top();
            S.pop();
        } 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.push({x,it.x,it.y});
            }
        }
    }
}

int main() {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    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;
}