#include <bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define pii pair<int, int>
#define tpl tuple<int,int,int>
using namespace std;

const string fn("apm");

ifstream in(fn + ".in");
ofstream out(fn + ".out");

#define cin in
#define cout out

const int MAX=2e5;

int n,m,x,y,w,t[MAX+5];
ll sum;
vector<tpl> v;
vector<pii> ans;

void read()
{
    cin>>n>>m;

    while(m--)
    {
        cin>>x>>y>>w;
        v.eb(w,x,y);
    }
}

int rad(int k)
{
    if(k==t[k]) return k;
    else return t[k]=rad(t[k]);
}

void marea_unire(int a,int b)
{
    if(t[a]<=t[b])
        t[b]=t[a];
    else t[a]=t[b];
}

void kruskal()
{
    for(int i=1;i<=n;i++)
        t[i]=i;
    sort(v.begin(),v.end());
    for(auto it: v)
    {
        tie(w,x,y)=it;

        int r1=rad(x),r2=rad(y);

        if(r1!=r2)
        {
            sum+=w;
            ans.eb(x,y);
            marea_unire(r1,r2);
        }
    }

    cout<<sum<<'\n'<<ans.size()<<'\n';
    for(auto x: ans)
        cout<<x.first<<' '<<x.second<<'\n';
}

int main()
{
    read();
    kruskal();
    return 0;
}