#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 200005
ifstream cin("apm.in");
ofstream cout("apm.out");

vector<pair<int, int> > graf[MAXN];
priority_queue<pair<int, int> > coada;
int n,m,i,j,x,y,c,nod,cost,cost_total;
int dp[MAXN], tata[MAXN];
bool fol[MAXN];

void prim(int k)
{
   dp[k] = 0;
   coada.push( make_pair(0, k ));
   while(!coada.empty())
   {
       nod=coada.top().second; fol[nod]=true;
       cost=-coada.top().first;
       coada.pop();

       if(dp[nod] < cost )
            continue;
       for(int i=0; i<graf[nod].size(); i++)
       {
           if(!fol[graf[nod][i].second] && dp[graf[nod][i].second] > graf[nod][i].first)
           {
               dp[graf[nod][i].second] = graf[nod][i].first;
               tata[graf[nod][i].second] = nod;
               coada.push(make_pair(-dp[graf[nod][i].second], graf[nod][i].second));
           }
       }
   }
   for(i=1; i<=n; i++)
     cost_total+=dp[i];

   cout<<cost_total<<"\n";
   cout<<n-1<<"\n";
   for(i=2; i<=n; i++)
    cout<<i<<" "<<tata[i]<<"\n";
}
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>c;
        graf[x].push_back( make_pair(c,y) );
        graf[y].push_back( make_pair(c,x) );
    }
    for(i=1; i<=n; i++)
        dp[i]=INF;
    prim(1);
}