#include <bits/stdc++.h>

using namespace std;

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

int n,m,x,y,c,i,j,cost,cmin,xmin,ymin;
set<int> s;
vector<pair<int,int>> v;
priority_queue<pair<int,pair<int,int>>> p;
vector<pair<int,int>> g[200001];

int main()
{
    cost=1001;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        if (c<cost)
        {
            cost=c;
            xmin=x;
            ymin=y;
        }
        g[x].push_back(make_pair(y,-c));
        g[y].push_back(make_pair(x,-c));
        s.insert(x);
        s.insert(y);
    }
    pair<int,pair<int,int>> l;
    v.push_back(make_pair(xmin,ymin));
    s.erase(xmin);
    s.erase(ymin);
    for (auto i: g[xmin])
        //if (s.find(i.first)!=s.end())
            p.push(make_pair(i.second, make_pair(i.first, xmin)));
    for (auto i: g[ymin])
        //if (s.find(i.first)!=s.end())
            p.push(make_pair(i.second, make_pair(i.first, ymin)));
    while (!s.empty())
    {
        l=p.top();
        p.pop();
        if (s.find(l.second.first)!=s.end())
        {
            if (s.find(l.second.second)==s.end())
            {
                for (auto i: g[l.second.first])
                {
                    //if (s.find(i.first)!=s.end())
                        p.push(make_pair(i.second, make_pair(i.first, l.second.first)));
                }
                v.push_back(make_pair(l.second.first, l.second.second));
                s.erase(l.second.first);
                cost-=l.first;
            }
        }
        else if (s.find(l.second.second)!=s.end())
        {
            for (auto i: g[l.second.second])
                {
                    //if (s.find(i.first)!=s.end())
                        p.push(make_pair(i.second, make_pair(i.first, l.second.second)));
                }
            v.push_back(make_pair(l.second.first, l.second.second));
            s.erase(l.second.second);
            cost-=l.first;
        }
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for (auto i: v)
    {
        fout<<i.first<<" "<<i.second<<'\n';
    }
    fout<<endl;
    return 0;
}