#include <fstream>
#include <vector>
#include <climits>
#include <queue>

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

int n,m,i,j,x,y,c,d[200005],k,tata[200005],sol,Min,poz;
bool viz[200005];
struct arc{
    int nod,cost;
};
vector <arc> g[200005];
struct cmp{
    bool operator()(arc &a, arc &b){
        return a.cost > b.cost;
    }
};
priority_queue <int, vector <arc>, cmp> h;

int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        g[x].push_back({y,c});
        g[y].push_back({x,c});
    }
    for(i=2;i<=n;i++)
        d[i]=INT_MAX;
    h.push({1,0});
k=n;
    while(k>0){
        int nod = h.top().nod;
        int cost=h.top().cost;
        h.pop();
        if(viz[nod])
            continue;
        viz[nod]=1;
        sol+=cost;
        for(j=0;j<g[nod].size();j++){
            int nou = g[nod][j].nod;
            int cost = g[nod][j].cost;
            if(!viz[nou] && d[nou]>cost){
                d[nou] = cost;
                tata[nou] = nod;
                h.push({nou,cost});
            }
        }
        k--;

    }
    fout<<sol<<'\n'<<n-1<<'\n';
    for(i=2;i<=n;i++)
        fout<<i<<' '<<tata[i]<<'\n';
    return 0;
}