#include <fstream>
#include <set>
#include <utility>
#include <vector>

using namespace std;

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

vector<pair<int,int> > v[200001];
multiset<pair<int,pair<int,int> > >  q;
int x,y,c,sum,st[200001],dr[200001];
bool visited[200001];

int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }

    x = 1;
    visited[1] = true;
    for(int i=1;i<n;i++)
    {
        visited[x] = true;
        for(int j=0;j<v[x].size();j++)
        {
            if(!visited[v[x][j].first])
            {
                q.insert(make_pair(v[x][j].second,make_pair(x,v[x][j].first)));
            }
        }
        while( visited[(*q.begin()).second.second])
            q.erase(q.begin());

        pair<int,pair<int,int> > f = *q.begin();

        dr[i] = x;
        st[i] = f.second.second;
        x = st[i];

        sum+=f.first;

    }
    fout<<sum<<' '<<n-1<<'\n';
    for(int i=1;i<n;i++)
        fout<<dr[i]<<' '<<st[i]<<'\n';
    fin.close();
    fout.close();
    return 0;
}