#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=200005;
vector <pair <int,int>> g[NMAX];
vector <int> parent;
bitset <NMAX> tree;
priority_queue <pair <int,pair <int,int>>> pq;
int n, m, x, y, w, c;

int main(){
    fin>>n>>m;
    parent.resize(n+1,0);

    for(int i=1;i<=m;i++){
        fin>>x>>y>>w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    pq.push({0,{0,1}});
    tree[0]=1;

    while(!pq.empty()){
        int d, a, b;
        d=-pq.top().first;
        a=pq.top().second.first;
        b=pq.top().second.second;
        pq.pop();
        if(!tree[b]){
            tree[b]=1;
            c+=d;
            parent[b]=a;
            //cout<<d<<' '<<a<<' '<<b<<endl;
            for(auto next:g[b]){
                if(!tree[next.first]){
                    pq.push({-next.second,{b,next.first}});
                }
            }
        }
    }

    fout<<c<<endl;
    fout<<n-1<<endl;
    for(int i=2;i<=n;i++){
        fout<<parent[i]<<' '<<i<<endl;
    }
    return 0;
}