#include <bits/stdc++.h>
#define Nmax 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct graph
{
    vector <pair <int,int> > v;
};
graph G[Nmax];
pair <int,int> sol[Nmax];
bitset <Nmax> viz;
class cmp
{
    bool ok;
    public:
    bool operator() (const pair<int,int> &x, const pair<int,int> &y) const
    {
        if(ok) return x.second<y.second;
        else return x.second>y.second;
    }
};
#define ppq priority_queue <pair<int,int>,vector <pair<int,int> >,cmp>
int main()
{int n,m,i,j,k,c;
f>>n>>m;
for(k=1;k<=m;k++)
{
    f>>i>>j>>c;
    G[i].v.push_back({j,c});
    G[j].v.push_back({i,c});
}
int sum=0;
k=0;
ppq pq;
#define nod first
#define cost second
int node=1;
viz[1]=true;
pair <int, int > ans;
while(k<n-1)
{
    for(i=0;i<G[node].v.size();i++)
    if(!viz[G[node].v[i].nod])
        pq.push(G[node].v[i]);
    ans=pq.top();
    pq.pop();
    while(viz[ans.nod])
    {
        ans=pq.top();
        pq.pop();
    }
    viz[ans.nod]=true;
    sum+=ans.cost;
    sol[++k]={node,ans.nod};
    node=ans.nod;
}
g<<sum<<'\n'<<k<<'\n';
for(i=1;i<=k;i++)
g<<sol[i].first<<' '<<sol[i].second<<'\n';

    return 0;
}