#include <fstream>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");
int n , m,cost,nrgasit=1;
bool vizitat[200001];
int tata[200001];
vector <pair<int, int > > v[200001];
set <tuple <int , int, int > > seti;
void prim (int nod)
{
    vizitat[nod] = 1;
    for (int i = 0;i<v[nod].size();++i)
    {
        int loc = v[nod][i].second;
        if (!vizitat[loc])
            seti.insert(make_tuple(v[nod][i].first,v[nod][i].second,nod));
    }
    bool gasit = 0;
    if (nrgasit==n)
        return;
    while (!gasit)
    {
        int x = get<1>(*seti.begin());
        if (!vizitat[x])
        {
            cost+=get<0>(*seti.begin());
            vizitat[x]=1;
            gasit = 1;
            tata[x] = get<2>(*seti.begin());
            seti.erase(seti.begin());
            nrgasit++;
            prim(x);
        }
        else
            seti.erase(seti.begin());
    }
}
int main ()
{
    in>>n>>m;
    tata[1]=0;
    for (int i=1;i<=m;++i)
    {
        int a,b,c;
        in>>a>>b>>c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    prim(1);
    out<<cost<<'\n'<<n-1<<'\n';
    for (int i = 1;i<=n;++i)
        out<<i<<' '<<tata[i]<<'\n';
}