#include <bits/stdc++.h>
using namespace std;
int n,m;
struct cows
{
    int val,poz,poz2;
};
cows cost[400005];
bool vf[200005];
int cnt=0;
bool vf2[200005];
vector<vector<int>>vc;

int Func(int j)
{
    int sum=0;
    priority_queue<pair<int,int>>pq;
    pq.push({cost[j].val*-1,j});
    while(!pq.empty())
    {

        int add=pq.top().first*-1;
        int pz=pq.top().second;
        int a=cost[pz].poz;
        int b=cost[pz].poz2;
        pq.pop();
        if(vf[a]==false || vf[b]==false)
        {
            vf2[pz]=true;
            sum+=add;
            cnt++;
            if(vf[a]==false)
            {
                for(int i=0;i<vc[a].size();i++)
                {
                    //cout<<vc[a][i];
                    if(vf2[vc[a][i]]==false)
                    pq.push({cost[vc[a][i]].val*-1,vc[a][i]});
                }
                vf[a]=true;
            }
            if(vf[b]==false)
            {
                for(int i=0;i<vc[b].size();i++)
                {
                    if(vf2[vc[b][i]]==false)
                    pq.push({cost[vc[b][i]].val*-1,vc[b][i]});
                }
                vf[b]=true;
            }
        }
    }
    return sum;
}
int main()
{
ifstream cin("apm.in");
ofstream cout("apm.out");
 cin>>n>>m;
 vc.resize(n+1);
 int minm=INT_MAX;
 int dot=0;
 for(int i=1;i<=m;i++)
 {
     cin>>cost[i].poz>>cost[i].poz2>>cost[i].val;
     vc[cost[i].poz].push_back(i);
     vc[cost[i].poz2].push_back(i);
     if(minm>cost[i].val)
     {
         minm=cost[i].val;
         dot=i;
     }
 }
 cout<<Func(dot)<<'\n';
 cout<<cnt<<'\n';
 for(int i=1;i<=m;i++)
 {
     if(vf2[i]==true)
     {
         cout<<cost[i].poz<<" "<<cost[i].poz2<<'\n';
     }
 }


    return 0;
}