#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#define NMax 1000005
#define mp make_pair
#define piii pair<int,pair<int,int>>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,sum=0,cnt=0,ok=1;

vector <pair<int,int>> vecini[NMax];
vector <int> mnc;
priority_queue <piii, vector<piii>, greater<piii>> pq;
queue <pair<int,int>> rez;
bitset<NMax> v;


int main()
{
    fin>>n>>m;
    for(int i=0; i<=n; i++)
        mnc.push_back(1005);
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        vecini[x].push_back({c,y});
        vecini[y].push_back({c,x});
    }
    int cur=1;
    while(cnt!=n-1)
    {
        for(auto i:vecini[cur])
        {
            if(v[i.second]==0 && i.first<mnc[i.second])
            {
                pq.push({i.first,{cur,i.second}});
                mnc[i.second]=i.first;
            }

        }
         v[cur]=1;
        while(!pq.empty() && v[pq.top().second.second]!=0)
            pq.pop();
        cur=pq.top().second.second;
        sum+=pq.top().first;
        cnt++;
        rez.push({cur,pq.top().second.first});


    }

    fout<<sum<<"\n"<<cnt<<"\n";
    while(!rez.empty())
    {
        fout<<rez.front().first<<" "<<rez.front().second<<"\n";
        rez.pop();
    }
    return 0;
}