#include <bits/stdc++.h>

#define NMAX 200000

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

typedef pair <int,pair<int,int>> data;
int t[NMAX];

vector <data> vec;

bool is_min(data x,data y)
{
    return (x.first<y.first);
}

int getParent(int u)
{
    int x=u;
    while(t[u]!=u)
        u=t[u];
    t[x]=u;

    return u;
}

int main()
{
    int n,m;
    fin>>n>>m;
    while(m--)
    {
        int u,v,w;
        fin>>u>>v>>w;
        data d=make_pair(w,make_pair(u,v));
        vec.push_back(d);
    }
    sort(vec.begin(),vec.end(),is_min);

    for(int i=1;i<=n;++i)
        t[i]=i;

    int w=0,nr=0;
    vector <pair <int,int>>res;

    for(int i=0;i<vec.size()&&nr<n-1;++i)
    {
        data x=vec[i];
        int p1=getParent(x.second.first);
        int p2=getParent(x.second.second);
        if(p1!=p2)
        {
            ++nr;
            w+=x.first;
            res.push_back(make_pair(x.second.first,x.second.second));
            t[p2]=p1;
        }
    }
    fout<<w<<'\n'<<n-1<<'\n';
    for(auto x:res)
    {
        fout<<x.first<<' '<<x.second<<'\n';
    }



    return 0;
}