#include <bits/stdc++.h>
using namespace std;
const int nmax=1e5+5;
ifstream f ("apm.in");
ofstream g("apm.out");
struct edge 
{
    int x,y,c;
};
bool cmp (edge a ,edge b)
{
    return a.c<b.c;
}
vector <edge> muchii;
int parent[nmax],height[nmax]; 
vector<pair<int,int>>ans;
int find (int nod)
{
    while(nod!=parent[nod])
    {
        nod=parent[nod];
    }
    return nod;

}
bool merge(int x ,int y)
{
    int p1=find(x),p2=find(y);
    if(p1==p2)
    return false;
    if(height[p1]>height[p2])
    {
        height[p1]++;
        parent[p2]=p1;
    }
    else
    {
         height[p2]++;
        parent[p1]=p2;
    }
    return true;
}



int main()
{   
    int n ,m;
    f>>n>>m;
    while(m--)
    {
        int x,y,c;
        f>>x>>y>>c;
        edge a;
        a.x=x, a.y=y,a.c=c;
        muchii.push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        height[i]=1;
    }
    int cost=0;
    sort(muchii.begin(),muchii.end(),cmp);
    for(auto it : muchii)
        if(merge(it.x,it.y))
            { cost+=it.c;
                ans.push_back({it.x,it.y});
            }
    g<<cost<<'\n'<<ans.size()<<'\n';
    for(auto it : ans)
        g<<it.first<<' '<<it.second<<'\n';



  


}