#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#define NMax 1000005
#define mp make_pair
#define piii pair<int,pair<int,int>>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,sum=0,cnt=0, mnc[NMax],ok=1;

vector <pair<int,int>> vecini[NMax];
queue <pair<int,int>> rez;
bitset<NMax> v;


int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
        mnc[i]=1005;
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        vecini[x].push_back({c,y});
        vecini[y].push_back({c,x});
    }
    int cur=1;
    while(ok)
    {
        ok=0;
        for(auto i:vecini[cur])
        {
            if(i.first<mnc[i.second])
                mnc[i.second]=i.first;
        }
        int mn=1005,ant=cur;
        v[cur]=1;
        for(int i=1; i<=n; i++)
        {
            if(mn>mnc[i] && v[i]==0)
            {
                mn=mnc[i];
                cur=i;
                ok=1;
            }
        }
        if(ok==1)
        {
            sum+=mn;
            cnt++;
            rez.push({ant,cur});
        }

    }

    fout<<sum<<"\n"<<cnt<<"\n";
    while(!rez.empty())
    {
        fout<<rez.front().first<<" "<<rez.front().second<<"\n";
        rez.pop();
    }
    return 0;
}