#include <fstream>
#include <queue>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream cin ("apm.in");
ofstream cout ("apm.out");

long long int t,m,c,u,v,curr,vec,x,y,ok,mask,cost,maxi,b,poz,pozc,n,k,i,j,sp[200005],a[200005],l[200005],r[200005],ll,rr,mij,mini,p,ans,nr,sum,mod=1e9+7;
string s;
//vector<int>g[200005];
queue<int>q;


struct graf
{
    int x,y,cost;
};

bool comp(graf a,graf b)
{
    return a.cost<b.cost;
}

vector<int> parent,rnk;

void union_find(int n)
{
    parent.resize(n);
    rnk.resize(n,0);
    for(int i=0; i<n; i++)
        parent[i]=i;
}

int findd(int u)
{
    if(parent[u]!=u)
        parent[u]=findd(parent[u]);
    return parent[u];
}

void unite(int u, int v)
{
    int rootu=findd(u);
    int rootv=findd(v);
    if(rootu!=rootv)
    {
        if(rnk[rootu]>rnk[rootv])
            parent[rootv]=rootu;
        else if(rnk[rootu]<rnk[rootv])
            parent[rootu]=rootv;
        else
        {
            parent[rootv]=rootu;
            rnk[rootu]++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    vector<graf>g(m);
    for(i=0; i<m; i++)
    {
        cin>>g[i].x>>g[i].y>>g[i].cost;
        g[i].x--;
        g[i].y--;
    }
    sort(g.begin(),g.end(),comp);

    union_find(n);

    ans=0;
    vector<pair<int, int>> arbore;

    for(i=0; i<m; i++)
    {
        u=g[i].x;
        v=g[i].y;
        cost=g[i].cost;
        if(findd(u)!=findd(v))
        {
            unite(u, v);
            ans+=cost;
            arbore.push_back({u+1,v+1});
            if(arbore.size()==n-1)
                break;
        }
    }
    cout<<ans<<endl;
    cout<<arbore.size()<<endl;
    for(const auto &muchie:arbore)
        cout<<muchie.first<<' '<<muchie.second<<endl;
    return 0;
}