#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<pair<int,int>,int> &x, const pair<pair<int,int>,int> &y) const
    {
        if(ok) return x.first.second<y.first.second;
        else return x.first.second>y.first.second;
    }
};
#define ppq priority_queue <pair <pair <int,int>,int>,vector < pair <pair <int,int>,int > >,cmp>
//#define ppq priority_queue <pair< pair<int,int> ,int> >
#define t second
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<pair <int, 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],node});
    ans=pq.top();
    pq.pop();
    while(viz[ans.first.nod])
    {
        ans=pq.top();
        pq.pop();
    }
    viz[ans.first.nod]=true;
    sum+=ans.first.cost;
    sol[++k]={ans.first.nod,ans.t};
    node=ans.first.nod;
}
g<<sum<<'\n'<<k<<'\n';
for(i=1;i<=k;i++)
g<<sol[i].first<<' '<<sol[i].second<<'\n';

    return 0;
}