#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main(){
    const int inf=1 << 30;
    ifstream cinr ("apm.in");
    ofstream cour ("apm.out");
    int m,n,a,b,y;
    cinr >> n;
    cinr >> m;
    vector< vector<int> > g(n+1);
    int p[n+1],d[n+1],c[n+1];
    for(int i=1; i<=m; i++){
            cinr >> a;
            cinr >> b;
            cinr >> y;
            g[a].push_back(b);
            g[a].push_back(y);
            g[b].push_back(a);
            g[b].push_back(y);
            }
    cinr.close();
    
    for(int i=1; i<=n; i++){
            p[i]=0;
            c[i]=0;
            d[i]=inf;
            }
    d[0]=inf+1;
    for(int i=1; i<=n; i++){
            y=0;
            for(int j=1; j<=n; j++){
                    if(c[j]==0 && d[j]<d[y]){ y=j; } 
                    }
            c[y]=1;
            for(int j=0; j<g[y].size(); j+=2){
                    if(c[g[y][j]]==0 && g[y][j+1]<d[g[y][j]]){
                                   p[g[y][j]]=y;
                                   d[g[y][j]]=g[y][j+1];
                                   }
                    }
            }
            y=0;
    for(int i=2; i<=n; i++){ y+=d[i]; }
    cour << y << "\n" << n-1 << "\n";
    for(int i=2; i<=n; i++){
            cour << p[i] << " " << i << "\n";
            }
    //cin.ignore(2);
    return 0;
    }