#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()(int &a, int &b){
        return d[a] > d[b];
    }
};
priority_queue <int, vector <int>, 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);

    while(!h.empty()){
        int nod = h.top();
        h.pop();
        if(viz[nod])
            continue;
        viz[nod]=1;
        sol+=d[nod];
        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);
            }
        }

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