#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,ok=1;

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


int main()
{
    fin>>n>>m;
    for(int i=0; i<=n; i++)
        mnc.push_back({1005,-1});
    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(cnt!=n-1)
    {
        for(auto i:vecini[cur])
        {
            if(v[i.second]==0 && i.first<mnc[i.second].first)
            {
                mnc[i.second].first=i.first;
                mnc[i.second].second=cur;
            }

        }
        int mn=1005;
        v[cur]=1;
        for(int i=1; i<=n; i++)
        {
            if(mn>mnc[i].first && v[i]==0)
            {
                mn=mnc[i].first;
                cur=i;
            }
        }

        sum+=mn;
        cnt++;
        rez.push({mnc[cur].second,cur});


    }

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