#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define VMAX 505
using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

vector<pair<int,int>> graf[VMAX];
//        cost, nod
vector<pair<int,int>> muchii_alese;
bool noduri_in_tree[VMAX];
set<pair<int,pair<int,int>>> q;
    // cost,  de unde , incotro plec
int nr_ramase_de_ales,suma_costuri;
void apm(int nod)
{
    int i,j,k;
    pair<int,pair<int,int>> x;
    for(i=0;i<graf[nod].size();i++)
    {
        q.insert({graf[nod][i].first,{nod,graf[nod][i].second}});
    }
    nr_ramase_de_ales--;
    noduri_in_tree[nod]=1;

    while(nr_ramase_de_ales)
    {
        x=*(q.begin());
        nod=x.second.second;
        q.erase(q.begin());
        if(noduri_in_tree[nod]==1)
            continue;

        noduri_in_tree[nod]=1;
        nr_ramase_de_ales--;
        muchii_alese.push_back({x.second.first,x.second.second});
        suma_costuri+=x.first;


        for(i=0;i<graf[nod].size();i++)
        {
            if(noduri_in_tree[graf[nod][i].second]==0)
                q.insert({graf[nod][i].first,{nod,graf[nod][i].second}});
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    long long int n,m,i,j,k,t,nr,maxim,minim,suma,hash_number;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>j>>k>>t;
        graf[j].push_back({t,k});
        graf[k].push_back({t,j});
    }
    nr_ramase_de_ales=n;
    apm(1);
    fout<<suma_costuri<<'\n'<<muchii_alese.size()<<'\n';
    for(auto it:muchii_alese)
        fout<<it.first<<' '<<it.second<<'\n';





    return 0;
}