#include <fstream>
#include <vector>
#define INF 1e9
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector <pair<int,int>> L[2000001];
int n ,m;
vector <pair<int,int >> sol;
int x ,y ,z;
pair<int ,int > cost[2000001];
int viz[2000001];
int main() {
    cin >> n >> m;
    for(int i =1 ;i <=m ;i ++)
    {
        cin>> x >> y >> z;
        L[x].push_back({y,z});
        L[y].push_back({x,z});
    }
    for(int i =1 ;i <=n ;i ++)
        cost[i] = {INF, 0};
    viz[1] = 1;
    for(auto i :L[1])
    {
        cost[i.first] ={i.second,1};
    }
    int suma = 0;
    for(int i =2 ;i <=n ;i ++)
    {
        pair <int ,int > minim;
        minim = {INF,INF};
        for(int j =1 ;j <=n;j ++)
            if(!viz[j])
                minim = min(minim, {cost[j].first,j});
        for(auto j:L[minim.second])
        {
            cost[j.first] = min(cost[j.first],{j.second, minim.second});
        }
        viz[minim.second] = 1;
        suma +=minim.first;
        sol.push_back({minim.second, cost[minim.second].second});
    }
    cout << suma<<'\n';
    cout << sol.size()<<'\n';
    for(auto i :sol)
        cout << i.first << " "<<i.second<<'\n';
    return 0;
}