#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
#define MAX 400000
struct muchie
{int x, y, cost;
} mu[MAX];
int tata[MAX];
vector <int> v;
bool cmp(muchie a, muchie b)
{
    return a.cost<b.cost;
}
int find_t(int x)
{
    if(tata[x]==x)
        return x;
    int t=find_t(tata[x]);
          tata[x]=t;
    return t;
}
int main()
{
    int n,m,i,j,ans=0;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>mu[i].x>>mu[i].y>>mu[i].cost;
    }
    for(int i=1; i<=n; i++)
        tata[i]=i;
    sort(mu+1,mu+m+1,cmp);
    for(int i=1; i<=m; i++)
    {
        if(find_t(mu[i].x)!=find_t(mu[i].y))
            //daca nodurile nu sunt deja unite, nu sunt conexe
        {
            ans=ans+mu[i].cost;
            tata[find_t(mu[i].y)]=find_t(mu[i].x);
            v.push_back(i);
        }
    }
    out<<ans<<'\n'<<v.size()<<'\n';
    while(!v.empty())
    {
        out<<mu[v.back()].x<<" "<<mu[v.back()].y<<'\n';
        v.pop_back();
    }

    return 0;
}