#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

vector <pair<int,int>> v[200002];
int cost[200002],parinte[200002];
bool inapm[200002];
int n,m,total;
priority_queue < pair <int,int> ,vector <pair <int,int> >, greater<pair <int,int> > > H;

void prim() {
    int nod,i,c,nou,c_muchie;
    for(i=1;i<=n;i++) {
        parinte[i]=-1;
        cost[i]=INT_MAX;
    }
    cost[1]=0;
    H.push(make_pair(0,1));
    while(H.size()) {
        auto best=H.top();
        H.pop();
        nod=best.second;
        inapm[nod]=1;
        for(i=0;i<v[nod].size();i++) {
            nou=v[nod][i].first;
            c_muchie=v[nod][i].second;
            if(inapm[nou]==0 and c_muchie<cost[nou]) {
                cost[nou]=c_muchie;
                parinte[nou]=nod;
                H.push(make_pair(cost[nou],nou));
            }

        }
    }

}

int main() {
    int i,j,x,y,c;
    in>>n>>m;
    for(i=1;i<=m;i++) {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    prim();
    int sum=0;
    for(i=2;i<=n;i++) {
        sum+=cost[i];
    }
    out<<sum<<'\n';
    out<<n-1<<'\n';
    for(i=2;i<=n;i++) {
        out<<i<<" "<<parinte[i]<<'\n';
    }
    return 0;
}