#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector <pair<int,int>> v[200001],sol;
set <pair<int,int>> d;
int a[200001],b[200001];
const int inf=1e9;
int main()
{
    set<pair<int,int>> :: iterator it;
    int n,m,i,x,y,rez=0,z;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    for(i=1;i<=n;i++)
        a[i]=inf;
    for(auto x : v[1])
    {
        a[x.first]=x.second;
        b[x.first]=1;
    }
    a[1]=-inf;
    for(i=2;i<=n;i++)
        d.insert(make_pair(a[i],i));
    for(i=2;i<=n;i++)
    {
        it=d.begin();
        rez+=(*it).first;
        sol.push_back(make_pair((*it).second,b[(*it).second]));
        a[(*it).second]=-inf;
        for(auto x : v[(*it).second])
        {
            if(x.second<a[x.first])
            {
                d.erase(d.find(make_pair(a[x.first],x.first)));
                d.insert(make_pair(x.second,x.first));
                a[x.first]=x.second;
                b[x.first]=(*it).second;
            }
        }
        d.erase(it);
    }
    cout<<rez<<'\n'<<sol.size()<<'\n';
    for(auto x : sol)
        cout<<x.first<<" "<<x.second<<'\n';
    return 0;
}