#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#if 0
#define cin fin
#define cout fout
#endif


using vi = vector<int>;
using pi = pair<int,int>;
using vpi = vector<pi>;

const int nmx = 1e2+1;
const int inf = 1e7;

vpi a[nmx];
int d[nmx],t[nmx];

int main()
{
    int n,m;
    fin >> n >> m;
    while(m--)
    {
        int u,v,c;
        fin >> u >> v >> c;
        a[u].emplace_back(v,c);
        a[v].emplace_back(u,c);
    }

    set<pi> q; // value, vertex
    fill(d,d+nmx,inf);
    q.emplace(0,1);
    d[1] = 0;
    vpi res;
    int cost = 0;
    for(int kk=0;kk<n;kk++)
    {
        if(q.empty())
        {/// no mst
            cout << kk;
            return -1;
        }
        auto it = q.begin();
        int v = it->second;
        int c = it->first;
        res.emplace_back(t[v],v);
        cost += c;

        q.erase(it);
        d[v] = -1;
        for(pi& to : a[v])
        {
            if(d[to.first] > to.second && d[to.first] !=-1)
            {
                q.erase({d[to.first],to.first});
                d[to.first] = to.second;
                t[to.first] = v;
                q.emplace(d[to.first],to.first);
            }
        }
    }
    fout << cost << "\n" << n-1 << "\n";
    for (int i=1;i<res.size();i++)
        fout << res[i].first << " " << res[i].second << "\n";
}